有一個1G大小的一個文件，內存限制大小是10M，有序返回頻數最高的50個詞，該怎麼做？

01-23

上午接到某公司內推的電話面試，問了一道題：
有一個2G大小的一個文件，內存限制大小是10M，有序頻數最高的50個詞。
這道題應該怎麼回答呢？（下面附我的回答，面試官不置可否，也不知道對不對）
我先問了最長單詞，他說32個字元。

（1）假定最長單詞是32個字母，就是32個位元組。把1G大小的文件hash為1000個文件，每個文件平均2M。考慮到某些單詞出現頻率較高但單詞較短，10M也基本夠用，不夠需要繼續劃分。
（2）用字典樹統計每個文件的頻率。
（3）維持一個容量為50的優先隊列（小頂堆實現），然後排序
————————————————————————————————
還有什麼方法？
（1）直接分成1000個文件分別trie樹統計頻率
（2）歸併結果
（3）堆遍歷，排序
—————————————————————————————————
哪種方法好？我沒答上來，說感覺上第一種好

能怎麼優化？我說把第一種封裝成（String,value）的類，用容量為50的紅黑樹（treeSet）,指定比較器比較value。。。後面都是問紅黑樹以及hash的設計問題了，略
感覺面試官不置可否，這道題應該怎麼答？哪種方法好？如何優化？

如果內存限制和正確性的要求都是嚴格的話，以下演算法可能適用：

1、內存里維護已出現單詞和它們的出現次數，組成有序對&<單詞，出現次數&>，用map維護。掃描這個大文件。每當內存用了10M的時候，將內存里的&<單詞，出現次數&>的有序對轉存至小文件里並清空內存，輸出時要按單詞的字典序排序。

2、第二遍，對所有小文件按單詞進行歸併。由於已經有字典序，歸併時幾乎沒有額外內存開銷，但要注意歸併順序以達到高效。

3、第三遍，維護一個大小為50的小根堆，並按單詞出現次數來組織堆。掃描一遍歸併後的文件，留在堆中的單詞即是最高頻的50個單詞。

簡而言之，這個演算法的核心就是一個外排序。

就是讓你編程實現 sort queries |uniq -c |sort -nr |head -50 嘛

Sort queries by their frequencies.

需要根據你的需求改一下 kMaxSize 和 nbuckets。

思考：找出 best case 和 worst case。

外部排序(直接上unix的sort就可以了)，然後掃一遍

面試被問到過這題，數字數量級大一些。

當時給的答案就是hash。根據單詞的hash分200個類，每個類寫進一個文件。寫完了按文件分別算。最後掃一遍找前50就行。典型的MapReduce的思路。

然後還被要求分析時間複雜度。

個人覺得這個就是標準答案了。

說IO開銷大的，你們外部排序或者用文件歸併真的大丈夫么。。。

讀一個單詞，以此單詞為文件名建一個文件（暫時認為文件名合法，當然不合法也可以替換實現），以後每讀一個，直接以單詞名打開文件，大小加一，最後以文件大小找前50，應該比較慢，呵呵，不過可以應對更小內存

（1）在外部排序選出結果，然後往內存讀寫

（2）數據分組進入內存，然後用trie統計個數（trie樹有10M的內存應該是夠的），

最後統計的話。。直接排序好啦，或者堆（速度稍微快一點點）啥的。。

trie樹

如果是英文單詞的話，用trie可以全內存操作了。最多100k個單詞，平均每個單詞8個字母，每個字母存一6位的內容，20個位的索引，22個位的數量，一共才4.8MB內存

感謝邀請，但我給不了啥建設性的意見。因為我認為在很多種情況下，這個事兒都做不了。需要確定很多細節情況，才好說使用什麼樣的方案。比如有些用gc的語言，你以為那塊兒內存釋放掉了，但開新的數組的時候，他會從新的地址申請，那樣你自己就無法控制內存使用的細節，更別說控制在10M之內了，另外有些統計內存使用的方式是以讀寫過的內存來算的，那就做不了。又比如假設Top 50存在很多相同詞頻的情況，應該如何處理？有可能把並列第50都存下10M都不夠。再比如，單個單詞的長度超過10M，那就不是一般的麻煩了。

當然以上極端問題都顯得比較矯情，但其他不矯情的方案別人都說的差不多了。各種文件處理的方案基本上都相當於利用文件系統建立一個Trie，而最後找Top 50基本上都是內存里乾的。

我對於很多有內存限制的問題不是很有好感，如果要把這題變得有趣，那麼應該是這樣，給出一個解決方案，然後你來出一個數據，讓這個方案出現問題，也許不小心一個ReadLine()，內存就超過10M了。

第一個做法你在1M的地方一切就可能把一個單詞切成兩半，答案就直接錯了。最簡單的做法不如用這100M寫個外部排序，再編譯一編就出結果了。

我能想到的就是分塊做排序 + string=&>int壓縮 + merge操作。。。

10M內存有點。。。是吧。。。

求正解。。。

最簡單的不是先花兩百多買跟4G的內存條嗎。

教你如何迅速秒殺掉：99%的海量數據處理面試題這裡有一系列講怎麼處理大數據的文章，挺不錯的，推薦下

這個問題有個蛋疼的地方，我一開始沒有發現，現在發現了：

如果你直接在內存裡面建立個字典什麼的……內存不夠啊有木有——不單單是讀文件內存不夠的問題了。

我的解決方案：

1、文件劃分成4M一段的小文件，每個文件只能小於4M，其中的所有單詞都是完整的。

2、開闢一段4M的內存作為字典

3、讀入一個小文件進行統計，統計結果寫入字典。

4、將統計得到的字典寫入硬碟什麼的，反正不能在內存裡面呆著了。

5、如果存在沒有讀過的小文件，重複步驟2，如果不存在，合併生成的字典。

幾個要點：

劃分，根據具體的方法不同，也是要消費空間的吧？這個程序在內存中也是要消費空間的吧？小文件讀取，這個也是要消費空間的吧？

總結：真要設計這樣的程序，問題多的很……主要是10M這個空間是在是太蛋疼了——連程序佔用空間也要考慮了……如果數量級大一點比如到100M，那麼這裡的很多問題就可以不用考慮了。

Selection sort的變形，在已知size=50的時候可以達到O(n).

讀取前大約2M的詞為字典（內存中留好計數的位置），刪除其中掉重複的，在留好的位置記錄重複次數或者1，在文件中刪除已讀取的這些詞。

從文件末尾開始，用接近8M內存開始讀取：在詞典中計數詞典中有的詞、在文件中刪除掉匹配的。讀完一遍文件將超過50次的詞另存文件，清空內存，重新開始程序。由於刪除了之前出現過的詞，文件越來越小，程序就越來越快。

第一步，將文件哈希到1000個文件中，同一個詞肯定在同一個文件中。

第二部，計算每個文件中單詞頻率，按照「單詞次數」格式輸出到文件中，如果大於10M繼續第一、二步

第二部，維護一個50大小的最小堆，順序讀取第二部的輸出文件，將次數作為堆比較的key，最後結果就是出現頻率最多的前50個單詞

我感覺你面的是百度。。。。

果斷字典樹吧。親。

被問爛了的IT公司面試題，網上搜索一大堆。。。

說說我的想法：

1.從第一個字元開始，然後第二個字元，……一直到第32個字元；

2.將字母相同的單詞歸到相同文件；

3.將第2步得到的所有文件循環執行1,2,3步，直到最長單詞的最後一個字元。

4.統計每個文件的單詞數量，取前50。

重複執行1,2,3步後，相同的單詞會放入同一個文件。

申請 10M 內存作內存池;

在這個內存池上構建 map&，比較操作不區分大小寫 ;內存分配器要手寫

循環 : 從文件取單詞,將 (單詞：1) 添加到MAP,如果已經存在，就增計數；如果OutOfMemory，就刪除計數最小的。