每晚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大概思路：
- 分而治之/hash映射：順序讀文件中，對于每個詞x，取hash(x)P00，然後按照該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k左右。如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續往下分，直到分解得到的小文件的大小都不超過1M。
- hash統計：對每個小文件，采用trie樹/hash_map等統計每個文件中出現的詞以及相應的頻率。
- 堆/歸并排序：取出出現頻率最大的100個詞（可以用含100個結點的最小堆），并把100個詞及相應的頻率存入文件，這時我們又得到了5000個文件。最後把這5000個文件進行歸并（類似與歸并排序）的過程。
類似這樣的方案應該有很多，我們共同去研究學習，經驗都是個人實踐總結出來的，以上僅代表個人觀點。以此分享給大家，不足之處望大家留言補充。
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
