缓慢的Swiftstring性能

我正试图解决回文分区问题。 你可以在https://leetcode.com/problems/palindrome-partitioning/find这个问题。

我想出了解决scheme:

func partition(_ s: String) -> [[String]] { var result: [[String]] = [] func dfs(string: String, partiton: [String]) { if string.characters.count == 0 { result.append(partiton) return } for length in 1...string.characters.count { let endIndex = string.index(string.startIndex, offsetBy: length-1) let part = string[string.startIndex...endIndex] if isPalindrome(part) { let leftPart = string[string.index(after: endIndex)..<string.endIndex] print("string: \(string) part: \(part) leftpart: \(leftPart)") dfs(string: leftPart, partiton: partiton + [part]) } } } func isPalindrome(_ s: String) -> Bool { if String(s.characters.reversed()) == s { return true } else { return false } } dfs(string: s, partiton: []) return result } 

但是performance不好。 超时限。

但是,与Python实现相同的想法可以通过:

 def partition(self, s): res = [] self.dfs(s, [], res) return res def dfs(self, s, path, res): if not s: res.append(path) return for i in range(1, len(s)+1): if self.isPal(s[:i]): self.dfs(s[i:], path+[s[:i]], res) def isPal(self, s): return s == s[::-1] 

这让我想知道如何改进快速实现,以及为什么快速实现比python慢​​。

Swift StringCharacter的集合, Character表示单个扩展字形集群,可以是一个或多个Unicode标量。 这使得像“跳过前N个字符”一些索引操作变慢。

但是第一个改进是“短路” isPalindrome()函数。 而不是完全build立反转的string,比较字符序列与其相反的序列,一旦发现差异停止:

 func isPalindrome(_ s: String) -> Bool { return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 } } 

s.characters.reversed()不会以相反的顺序创build一个新的集合,它只是从后到前枚举字符。 然而,在你的方法中使用String(s.characters.reversed())时,你强制为反转string创build一个新的集合,这使得它很慢。

对于110个字符的string

 let string = String(repeating: "Hello world", count: 10) 

这在我的testing中将计算时间从约6秒减less到1.2秒。

接下来,避免像索引计算

 let endIndex = string.index(string.startIndex, offsetBy: length-1) 

然后迭代字符索引本身:

 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 } 

计算时间现在是0.7秒。

下一步是完全避免string索引,并使用一组字符,因为数组索引是快速的。 更好的是,使用快速创build和引用原始数组元素的数组切片

 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 } 

计算时间现在是0.08秒。

如果您的string只包含“基本多语言平面”(即<= U + FFFF)中的字符,则可以使用UTF-16代码点:

 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 } 

110字符testingstring的计算时间现在为0.04秒。


所以有些提示可能会改善使用Swiftstring时的性能

  • 循序遍历字符/索引。 避免“跳跃”到第n个位置。
  • 如果您需要对所有字符进行“随机”访问,请首先将string转换为数组。
  • 使用string的UTF-16视图比使用字符视图更快。

当然这取决于实际的使用情况。 在这个应用程序中,我们能够将计算时间从6秒减less到0.04秒,这是150倍。