有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞?
分而治之/hash映射：順序讀文件中，對(duì)于每個(gè)詞x，取hash(x)%5000，然后按照該值存到5000個(gè)小文件(記為x0,x1,...x4999)中。這樣每個(gè)文件大概是200k左右。如果其中的有的文件超過(guò)了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過(guò)1M。
hash_map統(tǒng)計(jì)：對(duì)每個(gè)小文件，采用trie樹/hash_map等統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率。
堆/歸并排序：取出出現(xiàn)頻率最大的100個(gè)詞(可以用含100個(gè)結(jié)點(diǎn)的最小堆)后，再把100個(gè)詞及相應(yīng)的頻率存入文件，這樣又得到了5000個(gè)文件。最后就是把這5000個(gè)文件進(jìn)行歸并(類似于歸并排序)的過(guò)程了。
京公網(wǎng)安備 11010802030320號(hào)