慢速快速字符串性能 [英] Slow Swift String Performance
问题描述
我正在尝试解决Palindrome分区问题。您可以在 https://leetcode.com/problems/palindrome-partitioning/ 中找到该问题。 。
I am trying to solve the Palindrome Partitioning Question. You can find the question in 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
}
但表现不佳。时间限制超过。
But the performance is Bad. Time Limit Exceeded.
但是Python实现的相同想法可以通过：
But the same idea with Python implementation can pass:
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慢。
It make me wonder that how to improve the swift implementation and why the swift implementation is slower than python.
推荐答案
A Swift 字符串是字符的集合，以及字符表示单个扩展字形集群，可以是一个或多个
Unicode标量。这使得一些索引操作如跳过前N个字符变慢。
A Swift String is a collection of Characters, and a Character represents a single extended grapheme cluster, that can be one or more
Unicode scalars. That makes some index operations like "skip the first N characters" slow.
但第一个改进是短路 isPalindrome（ ）
函数。而不是完全构建反向字符串，比较
字符序列及其反转序列，并尽快停止
作为差异：
But the first improvement is to "short-circuit" the isPalindrome()
function. Instead of building the reversed string completely, compare
the character sequence with its reversed sequence and stop as soon
as a difference is found:
func isPalindrome(_ s: String) -> Bool {
return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }
}
s.characters.reversed（）不会以反向
顺序创建新集合，它只是从后到前枚举字符。
使用 String（s.characters.reversed（））但是在你的方法中，
你强制为反向字符串创建一个新的集合，
使它变慢。
s.characters.reversed() does not create a new collection in reverse
order, it just enumerates the characters from back to front.
With String(s.characters.reversed()) as in your method however,
you force the creation of a new collection for the reversed string,
that makes it slow.
对于110个字符的字符串
For the 110-character string
let string = String(repeating: "Hello world", count: 10)
这在我的测试中将计算时间从大约6秒减少到1.2秒。
this reduces the computation time from about 6 sec to 1.2 sec in my test.
接下来，避免像
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秒。
Computation time is now 0.7 sec.
下一步是完全避免字符串索引，并使用
一个字符数组，因为数组索引很快。更好的是，
使用数组切片，它们可以快速创建并引用原始的
数组元素：
The next step is to avoid string indexing totally, and work with an array of characters, because array indexing is fast. Even better, use array slices which are fast to create and reference the original array elements:
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 sec。
Computation time is now 0.08 sec.
如果您的字符串只包含基本多语言平面中的字符（即< = U + FFFF），那么您可以使用UTF-16代码点代替：
If your string contains only characters in the "basic multilingual plane" (i.e. <= U+FFFF) then you can work with UTF-16 code points instead:
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
}
计算时间现在是0.04 110字符测试字符串的秒。
Computation time is now 0.04 sec for the 110 character test string.
因此，在使用Swift字符串时可能会提高性能的一些提示是
So some tips which potentially can improve the performance when working with Swift strings are
- 按顺序迭代字符/索引。避免将
跳到第n位。 - 如果您需要随机访问所有字符，请先将字符串
转换为数组。 - 使用字符串的UTF-16视图比使用字符视图工作
要快。
当然这取决于实际的用例。在这个应用程序中，
我们能够将计算时间从6秒减少到0.04秒，
是150倍。
Of course it depends on the actual use-case. In this application, we were able to reduce the computation time from 6 sec to 0.04 sec, that is a factor of 150.
这篇关于慢速快速字符串性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
