Swift字符串 vs [字符] 和性能

Question

Swift字符串 vs [字符] 和性能

3

从一开始Swift字符串就很棘手，因为它们能够正确地使用UTF，并且有一个来自Apple的标准示例：

    let cafe1 = "Cafe\u{301}"
    let cafe2 = "Café"
    print(cafe1 == cafe2)
    // Prints "true"

这意味着比较具有一些隐含的逻辑，并不仅仅是简单地比较两个内存区域是否相同。我曾经见过一些建议将字符串拆分成[Character]，因为这样做会使所有与Unicode相关的转换只发生一次，然后所有操作都更快。此外，字符串不一定使用连续的内存区域，这使得它们相比字符数组更昂贵。

简而言之，我在leetcode上解决了这个问题：https://leetcode.com/problems/implement-strstr/，并尝试了不同的方法：KMP、字符数组和字符串。令我惊讶的是，字符串是最快的。

原因是什么？KMP有一些预处理工作，总体效率较低，但为什么字符串比[Character]更快？这是某个Swift版本的新功能还是我在概念上遗漏了什么？

下面是参考用的代码：

[Character]，8毫秒，15MB内存

    func strStr(_ haystack: String, _ needle: String) -> Int {
        guard !needle.isEmpty else { return 0 }
        guard haystack.count >= needle.count else { return -1 }
        
        var result: Int = -1
        
        let str = Array(haystack)
        let pattern = Array(needle)
        
        for i in 0...(str.count - pattern.count) {
            if str[i] == pattern[0] && Array(str[i...(i + pattern.count - 1)]) == pattern {
                result = i
                break
            }
        } 
        
        return result 
    }

字符串，4毫秒(!!!)，14.5mb内存

    func strStr(_ haystack: String, _ needle: String) -> Int {
        guard !needle.isEmpty else { return 0 }
        guard haystack.count >= needle.count else { return -1 }
        
        var result: Int = -1
        
        for i in 0...(haystack.count - needle.count) {
            var hIdx = haystack.index(haystack.startIndex, offsetBy: i)
            if haystack[hIdx] == needle[needle.startIndex] {
                var hEndIdx = haystack.index(hIdx, offsetBy: needle.count - 1)
                if haystack[hIdx...hEndIdx] == needle {
                    result = i
                    break
                }
            }
        }
        
        return result 
    }

- Igor Kashin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob Napier · Accepted Answer

首先，我认为你可能有一些误解：

将字符串直接转换为[Character]，因为这样做可以使所有与Unicode相关的转换只发生一次，然后所有操作都更快

这并不太合理。`Character` 与 `String` 完全相同的问题。它仍然可能由组合或分解的 `UnicodeScalars` 组成，需要特殊处理才能实现相等。

此外，字符串不一定使用连续的内存区域

这也同样适用于数组。数组中没有任何保证内存是连续的。这就是为什么ContiguousArray存在的原因。

至于为什么 `String` 比手动编写的抽象更快，这应该是显而易见的。如果你可以轻松地在没有主要权衡的情况下超越 `String`，那么 stdlib 将实现 `String` 来完成这个任务。

对于String的机制，它不保证任何特定的内部表示方式，因此它严重依赖于您如何创建字符串。例如，小字符串可以被缩减到一个标记指针，它不需要任何内存（可以存储在寄存器中）。字符串可以存储在UTF-8中，但也可以存储在UTF-16中（这种方式非常快）。

当字符串与其他知道它们具有相同内部表示的字符串进行比较时，它们可以应用各种优化。这确实指向了您问题的一部分：

Array(str[i...(i + pattern.count - 1)])

这强制进行内存分配和复制，以创建一个由 str 转换成的新数组。如果您使用 Slice 而不是完整的数组副本，则可能会更好地完成此工作。在这种情况下，您几乎肯定会发现自己正好匹配了 String 的实现（使用 SubStr）。

但真正的教训在于，在一般情况下，你不太可能在其专业领域中击败 String。如果您恰好具有关于字符串的非常专业化的知识，那么我可以理解您能够击败通用的 String 算法。但是，如果您认为自己正在击败 stdlib 的任意字符串，那么为什么 stdlib 不会直接实现您正在做的事情（并利用对 String 的内部细节的了解来击败您）？