swift - 在亚线性时间内找到圣经中包含单词或短语的所有经文？

Question

我计划使用字典作为我的数据结构，其中键等于圣经中找到的所有单词，值存储一个整数数组，其中每个整数指向诗句数组的索引。我的实现看起来像这样:

let verses = [String]() //All verses in the bible
var dict = [String:[Int]]() //Data Structure

func fillDict(){
    for verseIndex in 0..<verses.count{
        let words = verses[verseIndex].componentsSeparatedByString(" ")
        for word in words{
            if let indexArray = dict[word]{
                var newIndexArray = indexArray
                newIndexArray.append(verseIndex)
                dict[word] = newIndexArray
            }else{
                let arr = [verseIndex]
                dict[word] = arr
            }
        }
    }
}

填充字典显然非常慢。我正在寻找更快的实现或不同的数据结构来保证亚线性搜索时间。任何帮助将不胜感激。

Answer 1

TL; DR:Swift 的数组是写时复制的。使用 NSMutableArray 避免复制。

<小时/>

Swift 的数组是值类型。要将新元素追加到长度为 9 的数组中，需要分配一个容量为 10 的数组，复制前 9 个元素，并将新元素分配给最后一个槽。这当然需要很多周期。为了进行演示，让我们稍微修改一下您的代码并通过 Instruments 运行它，以了解为什么花了这么长时间:

let bible = try String(contentsOfFile: "King James Bible.txt")
let verses = bible.componentsSeparatedByCharactersInSet(.newlineCharacterSet())

func fillDict1() -> [String: [Int]] {
    var dict = [String: [Int]]()

    for verseIndex in 0..<verses.count{
        let words = verses[verseIndex].componentsSeparatedByString(" ")
        for word in words{
            if let indexArray = dict[word]{
                var newIndexArray = indexArray
                newIndexArray.append(verseIndex)
                dict[word] = newIndexArray
            } else {
                let arr = [verseIndex]
                dict[word] = arr
            }
        }
    }

    return dict
}

fillDict1()

(我使用了 Project Gutenberg 上提供的 King James Bible。我知道 verses 数组没有正确的经文分解，但这与当前的问题无关。)

选择产品 > 配置文件 (Cmd + I)，然后选择时间分析器。以下是 3 个最昂贵的电话:

Running Time        Self (ms)   Symbol Name
6464.0ms   61.8%    5.0         specialized Array._copyToNewBuffer(Int) -> ()
1093.0ms   10.4%    6.0         String.componentsSeparatedByString(String) -> [String]
896.0ms    8.5%     0.0         specialized _VariantDictionaryStorage.updateValue(B, forKey : A) -> B?
...
(Total: 9736ms)

正如预期的那样，为新数组分配新内存需要花费大量时间。幸运的是，Apple 已经在 NSMutableArray 中为您解决了这个问题:

func fillDict2() -> [String: [Int]] {
    var tmp = [String: NSMutableArray]()

    for (verseIndex, verse) in verses.enumerate() {
        let words = verse.componentsSeparatedByString(" ")
        for word in words {
            let indexArray = tmp[word] ?? NSMutableArray()
            indexArray.addObject(verseIndex)

            tmp[word] = indexArray
        }
    }

    var dict = [String: [Int]]()
    for (word, verses) in tmp {
        dict[word] = ((verses as NSArray) as! [Int])
    }

    return dict
}

再次通过 Instruments 运行 fillDict2()，这就是我得到的结果:

Running Time        Self (ms)   Symbol Name
916.0ms   21.5%     8.0         String.componentsSeparatedByString(String) -> [String]
783.0ms   18.4%     27.0        specialized _VariantDictionaryStorage.nativeUpdateValue(B, forKey : A) -> B?
754.0ms   17.7%     0.0         specialized _VariantDictionaryStorage.updateValue(B, forKey : A) -> B?
...
(Total: 3911ms)

速度提高了 2.5 倍!显然您还可以寻找其他优化。这是一场永无止境的游戏。您必须确定什么时候它对您来说足够快。