我正在尝试解决回文分割问题。您可以在 https://leetcode.com/problems/palindrome-partitioning/ 中找到问题.
然后我想出了解决方案:
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
}
但是性能很差。超过时间限制。
但是同样的思路用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]
这让我想知道如何改进 swift 实现以及为什么 swift 实现比 python 慢。
最佳答案
一个 Swift String 是一个 Character 的集合，一个 Character 代表一个扩展的字素簇，可以是一个或多个
Unicode 标量。这使得一些索引操作(如“跳过前 N 个字符”)变慢。
但第一个改进是“短路”isPalindrome()
功能。不是完全构建反转字符串，而是比较
具有相反顺序的字符序列并尽快停止
发现差异:
func isPalindrome(_ s: String) -> Bool {
return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }
}
s.characters.reversed() 不反向创建新集合
顺序，它只是从后到前枚举字符。
但是，在您的方法中使用 String(s.characters.reversed()) ，
您强制为反转的字符串创建一个新集合，
这让它变慢了。
对于 110 个字符的字符串
let string = String(repeating: "Hello world", count: 10)
在我的测试中，这将计算时间从大约 6 秒减少到 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 秒。
下一步是完全避免字符串索引，并使用 一个字符数组，因为数组索引很快。更好的是， 使用数组 切片 可以快速创建和引用原始数据 数组元素:
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 秒。
如果您的字符串仅包含“基本多语言平面”中的字符(即 <= 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 个字符的测试字符串，现在的计算时间为 0.04 秒。
因此，在使用 Swift 字符串时可能会提高性能的一些技巧是
- 按顺序迭代字符/索引。避免“跳跃” 到第 n 个位置。
- 如果您需要“随机”访问所有字符，请将字符串转换为 首先到一个数组。
- 处理字符串的 UTF-16 View 比处理字符串更快 使用字符 View 。
当然，这取决于实际用例。在这个应用程序中， 我们能够将计算时间从 6 秒减少到 0.04 秒， 这是 150 的因数。
关于ios - 缓慢的 Swift 字符串性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41038714/