Qt - 在200k字典中搜索字符串

Question

所以，我有這個文本文件（用Aspell生成），其中包含200 000個字。它將被用於一個可疑的遊戲，來檢查這個單詞是否合法。這意味着，很可能會有很多檢查單詞不在那裏，我想知道最有效的方法是什麼。

1. 檢查每行文本行將每次檢查需要200 000次迭代，所以這將是我的最後選擇。

2. 獲取QList中的所有單詞，並使用Qlist :: contains（）函數（或QList :: indexOf（），因爲我認爲我使用的是Qt4.8）。我不知道這樣做的效率，而且會有相當多的內存使用。

3. 使用散列表。我真的不確定它是如何工作的，所以如果任何人都可以告訴我有提供的Qt數據類型，我可以做一些研究。

還有其他有效的方法嗎？目前傾向於QList方法，似乎最容易實現:)

Answer 1

您可以使用std::unordered_set，它通過散列表執行查找。 Qt的有它自己的實現它QSet

不要使用的QList或第一個文件遍歷方法，因爲這兩個數量級以上的散列表查找的速度較慢的訂單。

Answer 2

假設散列表是好的，使用散列表一定是最快的方法（因爲它是散列的簡單計算 - 因爲字符串可能不是很長，不應該花費太多時間 - 典型的英語單詞是大約5個字符長）。

有一個在此頁的關於如何哈希字符串QHash節爲例：http://doc.qt.digia.com/qq/qq19-containers.html

Answer 3

排序列表 - 一次性操作：保存排序，或者啓動程序時對其進行排序 - 並使用二進制搜索。查找任何 200,000個單詞中的單詞將平均取17.6個查找，大約四個第一操作只需要檢查單個字符。