在Objective-C中搜索字符串的最快方法是什麼？

我正在爲iOS應用程序實現一種自動完成。我用於自動完成值的數據是一個包含大約100,000個字符串的逗號分隔文本文件。這是我現在正在做的：在Objective-C中搜索字符串的最快方法是什麼？

閱讀文本文件，並創建一個NSArray與100,000 NSString。
當用戶類型，不要[array containsObject:text]

肯定有做這種查找更好/更快的方式。有什麼想法嗎？

2012-07-20 user1007895

您可以試着跳過甚至不匹配第一個字母的字符串，如果您的單詞是斑馬，則從蘋果搜索到酸奶沒有任何意義。我不確定實現這個的最佳方式，也許是一個多維數組？第一維可以是第一個字母，第二個維度第二個字母等，直到像第三個或第四個字母一樣，那麼你可以只包含該單詞的其餘部分。 – 2012-07-20 20:40:37

如果你不需要排序，我認爲當檢查它是否包含一個對象時，這些集合會更快。它仍然沒有爲字符串優化。你應該看看二叉樹等東西，如果你需要製作自定義代碼，不管你使用的平臺/語言如何，一般的方法都是類似的。 – 2012-07-20 20:42:04

有*總是*更快的方式。但是，您在用戶界面中看到滯後嗎？儘管使用了簡單的搜索算法，但我已經完成了與自動完成相同的事情（使用較小的輸入數組），並且沒有可見的延遲。 – kubi 2012-07-20 21:13:33

絕對有！但它不是「在Objective-C中」：很可能，您需要自己編寫代碼。

這個想法是將您的字符串列表轉換爲suffix tree，這是一種數據結構，可以讓您通過前綴非常快地進行搜索。在後綴樹中搜索可能的完成速度非常快，但結構本身並不容易構建。在互聯網上快速搜索發現，目標C中沒有現成的實施方案，但是如果您沒有特別緊迫的時間，則您可能能夠編寫port an implementation in another language,use a C implementation，甚至可以編寫自己的文章。

也許更簡單的方法是按字母順序對字符串進行排序，然後對目前輸入的前綴執行二分法搜索。雖然效率不及後綴樹，但排序後的數組方法對於100K字符串是可以接受的，因爲您可以在17個檢查中找到正確的位置。

來源

2012-07-20 20:42:34 dasblinkenlight

+1指出Objective-C是C，當你觀察性能密集型任務時，你不應該害怕下降到C :)我也將第二個可能是最容易實現的二叉樹。 – Taum 2012-07-20 20:58:11

+1只是愛你的答案 – Omarj 2013-05-21 08:05:27

NDTrie（https://github.com/nathanday/ndtrie）和PJTernarySearchTree（https://github.com/peakji/PJTernarySearchTree）恰恰就是Objective-C中的！ – 2014-04-18 19:58:36

最簡單的可能是二分查找。請參閱-[NSArray indexOfObject:inSortedRange:options:usingComparator:]。

我特別想嘗試這樣的事：

預排序的數組，你保存到文件
當加載陣列，可能@selector(compare:)（如果你擔心它意外排序或者某些邊緣情況下的Unicode排序順序發生變化）。假設數組已經大部分已經排序，這應該大致爲O（n）。
要找到第一個潛在的匹配，[array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
走下數組，直到條目不再包含searchString作爲前綴。你可能想要做的情況下/讀音符號/寬度不敏感的比較，以確定它是否是一個前綴（NSAnchoredSearch | NSCaseInsensitiveSearch | NSDiacriticInsensitiveSearch | NSWidthInsensitiveSearch）

這可能不是「正確」處理所有語言環境（土耳其特別）但是既不會用localizedCompare:代替compare:，也不會天真的字符串摺疊。（它只有9條線，但需要大約一天的工作時間才能找到正確的，並且有大約40行代碼和200行測試，所以我可能不應該在這裏分享它。）

來源

2012-07-20 20:59:14

在Objective-C中搜索字符串的最快方法是什麼？

回答

相關問題