在亞線性時間內找到所有在聖經中包含單詞或短語的經文？

我打算使用字典作爲我的數據結構，其中鍵等於聖經中找到的所有單詞，並且這些值存儲整數數組，其中每個整數都指向一個經文數組的索引。我的執行看起來像這樣：在亞線性時間內找到所有在聖經中包含單詞或短語的經文？

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 
      } 
     } 
    } 
}

填寫字典顯然非常緩慢。我正在尋找更快的實施方式或不同的數據結構，以保證亞線性搜索時間。任何幫助將不勝感激。

來源

2016-06-21 twentyfauxcarat

推測，你只需要構建一次你的數據結構。然後，您可以將字典保存在磁盤上，將其作爲應用程序的一部分構建，並直接從文件加載。（或者如果你需要更好的搜索，你可以用預加載的數據庫做同樣的事情。） –

這就是我原本打算做的事情。我主要的抱怨是在填寫字典的時候。我希望我能避免它。謝謝。 – twentyfauxcarat

TL; DR： Swift的數組是寫時拷貝的。避免使用NSMutableArray進行復制。

Swift的數組是值類型。要將一個新元素附加到長度爲9的數組，它需要分配一個容量爲10的數組，將前9個複製過來，並將新元素分配給最後一個插槽。這當然需要很多週期。爲了演示，讓我們稍微修改您的代碼並運行它通過儀器得到的是什麼要花這麼長的一個想法：

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我知道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)

正如所料，爲新陣列分配新內存需要很長時間。通過儀器

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 
}

運行fillDict2()再次這裏是我得到的：幸運的是，蘋果已經在NSMutableArray解決了這個問題，你

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.5x的速度更快！顯然你也可以尋找其他的優化。這是一個永無止境的遊戲。你必須確定它對你來說足夠快。

來源

2016-06-23 02:34:52

謝謝，非常感謝！我會努力看看我能否再優化一點;） – twentyfauxcarat

在亞線性時間內找到所有在聖經中包含單詞或短語的經文？

回答

相關問題