每晚10點，捕獲技術思考和創業資源洞察

“分而治之”( Divide and conquer)方法(又稱“分治術”) ，是有效算法設計中普遍采用的一種技術。

有一個1G大小的一個文件，里面每一行是一個英文單詞，詞的大小不超過16字節，內存限制是1M。請設計一個算法思路，返回頻數最高的100個詞.

初步一看，要處理的文件大小1G，可內存卻只有1M。我們知道1G的文件用1M的內存空間處理不太現實。按照1M的上限來計算，假設每個單詞都為16個字節，那么1M的內存可以處理多少個單詞？

我們來計算下，1M = 1024 KB = 1024 * 1024 B 。1M / 16B = 2^16個單詞，那么1G大概有多少個單詞呢？有2^26個單詞，但是實際中應該不止，因為我們是按照最大單詞長度來計算的，有可能有的單詞只有兩個字母。

方案1大概思路：

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

類似這樣的方案應該有很多，我們共同去研究學習，經驗都是個人實踐總結出來的，以上僅代表個人觀點。以此分享給大家，不足之處望大家留言補充。