慢的Swift字符串性能

Question

我正在尝试解决回文分割问题。您可以在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慢。

- Learing

Answer 1

在 Swift 中，String 是一个由 Character 组成的集合，而一个 Character 表示一个扩展字形簇（extended grapheme cluster），可以由一个或多个 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视图可能比使用字符视图更快。

当然，这取决于实际用例。在此应用程序中，我们将计算时间从6秒减少到了0.04秒，即缩短了150倍。

- Martin R