比方說，您給了一個巨大的文件，比如1GB。該文件在每行中包含一個單詞（總共有n個單詞），並且您希望在文件中找到k個最頻繁的術語。在文件中查找k個最常見的單詞 - 內存使用情況
現在，假設你有足夠的內存來存儲這些話，有什麼更好的方式來處理在減少大O的複雜性內存使用和恆定的開銷方面的問題嗎？我相信有兩種基本算法可供使用：
這是一個更好的辦法？
另外：如果你沒有爲一個哈希表/特里足夠的內存（即有限的10MB內存左右），那麼什麼是最好的辦法？
對於有限的內存選項，您可以先快速對列表進行排序，然後只需在其中添加k個項目來填充散列表。然後你需要一個計數器來知道你正在檢查的當前單詞中有多少項 - 如果它高於那麼你用當前項目替換散列表中的最低項。
這可能會工作確定爲初步名單，但將不僅僅是掃描的完整列表，並填充一個哈希表的計數慢。
你爲什麼要冒泡排序？使用Quicksort不會進行某種外部排序會更有效嗎？ – user1921187
是的，我的錯誤 - 應該是快速排序！首先排序意味着你不必用計數來維護一個單詞列表 - 如果每個單詞都是唯一的，這可以使記憶成倍增加，排序可以將它保持爲n + k。 –
有限的內存快速排序非常糟糕（請記住，您無法將文件存儲在內存中）。如果有的話，你應該使用外部排序（這通常是合併排序的變體）。然而，它很少做 - 哈希在磁盤上的數據通常效率更高，需要更少的磁盤尋求 – amit
這是更有效的關於常數非常依賴。一方面，trie爲插入所有元素提供了嚴格的時間複雜度O(N)，而在最壞的情況下，散列表可能衰減到二次時間。
在另一方面，嘗試都不是很有效的，當談到cache - 每個尋求需要O(|S|)隨機存取內存請求，這可能導致性能顯著衰減。
這兩種方法都是有效的，我認爲在選擇一種方法時需要考慮多種因素，如最大latency（如果是實時系統），吞吐量和開發時間。
如果平均情況下性能是重要的，我會建議生成一堆文件，並運行statistical analysis哪種方法更好。簽名測試是使用中的藝術假設測試的事實上的狀態。
關於嵌入式系統：這兩種方法仍然是有效的，但在這裏： 在特里樹的每個「節點」（或一羣節點）將在磁盤上而不是在RAM中。請注意，這意味着對於特洛伊O（| S |）隨機訪問每個項目的磁盤查詢，這可能是緩慢的。
哈希計算解決方案，您有10MB，讓我們說，他們可以使用5MB出這些爲指針到磁盤的哈希表。假設您可以在這5MB存儲500個不同的磁盤地址（這裏是悲觀分析），這意味着每次哈希查找後您都剩下5MB的時間來加載一個存儲桶，並且如果您有500個存儲桶，並且負載因子爲0.5，則表示您可以存儲500 * 5MB * 0.5〜1.25GB> 1GB的數據，因此使用散列表解決方案，所以使用散列表- 每次查找將只需要O(1)隨機磁盤查找爲了查找包含相關字符串。
請注意，如果它仍然不夠，我們可以重新掃描指針表，這與虛擬內存機制中的paging table中正在執行的操作非常相似。
由此我們可以得出結論，對於嵌入式系統，散列解決方案對於大多數情況下更好（注意它可能仍然遭受最壞情況下的高延遲，這裏沒有銀彈）。
PS，radix tree通常是更快和更緊湊然後特里結構，但是從字典樹的相同的副作用比較對散列表的受到（雖然少顯著當然）。
因此，基本上在無限的內存的情況下，你說，哈希是依賴於個案的？如果是這樣，什麼情況會使數據結構更好？ 在第二種情況下，是否有更好的方法來處理問題而不是線索或散列？ – user1921187
@ user1921187：以下是一些示例：如果您的系統具有非常差的散列機制，或者根本沒有緩存 - 嘗試的「缺點」不再相關 - 請使用它。其他示例 - 如果每個查詢都有嚴格的時間限制 - 您無法承受哈希解決方案衰減到二次時的低概率，並且您可能選擇了trie，即使它在平均情況下速度較慢。此外，嘗試提供了一些哈希表不需要 - 順序。如果需要，您可以輕鬆地遍歷嘗試，並且前綴搜索對於嘗試也很容易，但我認爲這不是一個問題。 – amit
@ user1921187：關於第二種情況（嵌入式系統） - 替代方法是排序和迭代。然而，它通常需要更多的磁盤尋道（我認爲〜* 2個磁盤尋道，但如果這是一個問題，我可以在稍後進行數學計算），然後是散列解決方案。由於在這種情況下，磁盤IO是瓶頸，這意味着排序和迭代將消耗更多時間 – amit
你開車存儲中間結果嗎？如果爲真：
你可能有一些元結構。 和一組hashetable。 你讀了一部分數據（而你的大小散列表< 3 MB）並填充散列表。當你的尺寸大於3mb時，你可以保存在磁盤上。 如果你限制的是10MB的散列表大小是3MB（例如）。
meta描述你的哈希表。 在元你可以存儲一些獨特的單詞和所有單詞的數量在這個散列和一個世界的最大數量！ i
此後。 您可以從磁盤加載哈希表併合並。
例如，您可能會按照哈希表中唯一字的升序或一個世界的最大數量來加載散列表。 在這一步你可以使用一些啓發式。
粗略地說，你期望在1GB文件中有多少不同的單詞？ – NPE
我並不特別期待任何事情。這個問題可以用現實世界的術語來重新編寫，如從搜索列表或類似的東西中找到前10個搜索條件，所以我想它會遵循某種概率分佈，但我沒有設置特定的搜索條件。 – user1921187