A Swift String là tập hợp Character s và Character đại diện cho một cụm đồ thị mở rộng duy nhất, có thể là một hoặc nhiều vô hướng Unicode. Điều đó làm cho một số hoạt động chỉ mục như "bỏ qua ký tự đầu tiên" chậm.
Nhưng cải tiến đầu tiên là "ngắn mạch" chức năng isPalindrome() . Thay vì xây dựng chuỗi đảo ngược hoàn toàn, so sánh chuỗi ký tự với chuỗi đảo ngược của nó và dừng lại càng sớm như một sự khác biệt được tìm thấy:
func isPalindrome(_ s: String) -> Bool {
return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }
}
s.characters.reversed() không tạo ra một bộ sưu tập mới trong ngược trật tự, nó chỉ liệt kê các nhân vật từ sau ra trước. Tuy nhiên, Với String(s.characters.reversed()) như trong phương pháp của bạn, bạn bắt buộc tạo bộ sưu tập mới cho chuỗi bị đảo ngược, làm cho nó chậm.
Đối với chuỗi 110 ký tự
let string = String(repeating: "Hello world", count: 10)
này làm giảm thời gian tính toán từ khoảng 6 giây đến 1,2 giây trong thử nghiệm của tôi.
Tiếp theo, tránh tính toán chỉ số như
let endIndex = string.index(string.startIndex, offsetBy: length-1)
và lặp qua các chỉ số nhân vật riêng của mình thay vì:
func partition(_ s: String) -> [[String]] {
var result: [[String]] = []
func dfs(string: String, partiton: [String]) {
if string.isEmpty {
result.append(partiton)
return
}
var idx = string.startIndex
repeat {
string.characters.formIndex(after: &idx)
let part = string.substring(to: idx)
if isPalindrome(part) {
let leftPart = string.substring(from: idx)
dfs(string: leftPart, partiton: partiton + [part])
}
} while idx != string.endIndex
}
func isPalindrome(_ s: String) -> Bool {
return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }
}
dfs(string: s, partiton: [])
return result
}
thời gian tính toán hiện nay 0,7 giây là.
Bước tiếp theo là tránh lập chỉ mục chuỗi hoàn toàn và làm việc với một mảng ký tự, vì lập chỉ mục mảng nhanh. Thậm chí tốt hơn, sử dụng mảng lát mà là nhanh chóng để tạo ra và tham khảo các yếu tố mảng ban đầu:
func partition(_ s: String) -> [[String]] {
var result: [[String]] = []
func dfs(chars: ArraySlice<Character>, partiton: [String]) {
if chars.isEmpty {
result.append(partiton)
return
}
for length in 1...chars.count {
let part = chars.prefix(length)
if isPalindrome(part) {
let leftPart = chars.dropFirst(length)
dfs(chars: leftPart, partiton: partiton + [String(part)])
}
}
}
func isPalindrome(_ c: ArraySlice<Character>) -> Bool {
return !zip(c, c.reversed()).contains { $0 != $1 }
}
dfs(chars: ArraySlice(s.characters), partiton: [])
return result
}
thời gian tính toán hiện nay 0,08 giây là.
Nếu chuỗi của bạn chỉ chứa các ký tự trong "mặt phẳng đa ngôn ngữ cơ bản" (tức là< = U + FFFF) sau đó bạn có thể làm việc với các điểm UTF-16 mã thay vì:
func partition(_ s: String) -> [[String]] {
var result: [[String]] = []
func dfs(chars: ArraySlice<UInt16>, partiton: [String]) {
if chars.isEmpty {
result.append(partiton)
return
}
for length in 1...chars.count {
let part = chars.prefix(length)
if isPalindrome(part) {
let leftPart = chars.dropFirst(length)
part.withUnsafeBufferPointer {
dfs(chars: leftPart, partiton: partiton + [String(utf16CodeUnits: $0.baseAddress!, count: length)])
}
}
}
}
func isPalindrome(_ c: ArraySlice<UInt16>) -> Bool {
return !zip(c, c.reversed()).contains { $0 != $1 }
}
dfs(chars: ArraySlice(s.utf16), partiton: [])
return result
}
thời gian tính toán tại là 0,04 giây cho chuỗi kiểm tra 110 nhân vật.
Vì vậy, một số lời khuyên mà khả năng có thể cải thiện hiệu suất khi làm việc với chuỗi Swift là
- lặp qua các ký tự/chỉ số tuần tự. Tránh "nhảy" đến vị trí thứ n.
- Nếu bạn cần quyền truy cập "ngẫu nhiên" vào tất cả các ký tự, trước tiên hãy chuyển đổi chuỗi thành mảng.
- Làm việc với chế độ xem UTF-16 của chuỗi có thể nhanh hơn khi đang hoạt động với chế độ xem ký tự.
Tất nhiên nó phụ thuộc vào trường hợp sử dụng thực tế. Trong ứng dụng này, , chúng tôi có thể giảm thời gian tính toán từ 6 giây xuống 0.04 giây, là hệ số 150.