每晚10點，捕捉技術思維，洞察創(chuàng)業(yè)資源。

“分而治之”方法(也稱為“分而治之”)是有效算法設計中廣泛使用的技術。

有一個文件，大小為1G，其中每行是一個英文單詞，字長不超過16字節(jié)，內(nèi)存限制為1M。請設計一個算法，返回出現(xiàn)頻率最高的100個單詞。

乍一看，要處理的文件大小是1G，但內(nèi)存只有1M。我們知道用1M內(nèi)存空處理1G文件是不現(xiàn)實的。按照1M的上限，假設每個字是16字節(jié)，1M內(nèi)存可以處理多少個字？

我們來計算一下，1m = 1024 kb = 1024 * 1024 b . 1m/16b = 2^16字數(shù)，那么1G有多少字呢？有2 ^ 26個單詞，但實際上應該不止這些，因為我們是按照最大單詞長度來計算的，有可能有些單詞只有兩個字母。

1 .方案的總體思路:

分而治之/hash映射：順序讀文件中，對于每個詞x，取hash(x)P00，然后按照該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k左右。如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M。hash統(tǒng)計：對每個小文件，采用trie樹/hash_map等統(tǒng)計每個文件中出現(xiàn)的詞以及相應的頻率。堆/歸并排序：取出出現(xiàn)頻率最大的100個詞（可以用含100個結點的最小堆），并把100個詞及相應的頻率存入文件，這時我們又得到了5000個文件。最后把這5000個文件進行歸并（類似與歸并排序）的過程。

類似的方案應該還有很多。我們要一起學習，一起學習，我們的經(jīng)驗是通過親身實踐總結出來的。以上僅代表個人觀點。我想把這個分享給大家，也希望大家可以留言補充自己的不足。