給我一把榔頭，滿世界都是釘子

一篇文章存成一個巨大的文件，總共大約有一億個單詞，要找出里面重復次數(shù)最多的。怎么做？ Hadoop是一把威力巨大的榔頭，在使用過Hadoop之后，看著任何東西都想把它給map reduce了。有一個關于Jeff Dean的小笑話，說在睡不著覺的時候，一般人是數(shù)羊，Jeff De

一篇文章存成一個巨大的文件，總共大約有一億個單詞，要找出里面重復次數(shù)最多的。怎么做？

Hadoop是一把威力巨大的榔頭，在使用過Hadoop之后，看著任何東西都想把它給map reduce了。有一個關于Jeff Dean的小笑話，說在睡不著覺的時候，一般人是數(shù)羊，Jeff Dean是map reduce他的羊群。所以，我的辦法是，把這個文件拆分成若干個小文件，在map過程用hash算法保證相同的單詞落入一個文件（這點很重要），計算單詞出現(xiàn)次數(shù)，在reduce過程取得重復次數(shù)最多的單詞來。

但是，真有必要這樣啰嗦嗎？

只有一億個單詞，簡單估算一下，一個字母占據(jù)兩個字節(jié)，假設單詞平均長度5，即便是最極端情況，這些單詞里面沒有重復，單詞本身也就消耗1G而已；而實際上一篇文章單詞的重復率是非常高的，這個數(shù)據(jù)量完全可以放在內存里面計算。還沒完，不一定非得要用Hash，如果借由Trie樹，可以節(jié)點壓縮，占用更少的空間。

這只是一個用榔頭來敲釘子的一個小例子而已，在我剛學算法的時候，那時候剛接觸外排序，這樣的問題我或許會第一反應使用外排序來做，在那個時候，這把榔頭就是外排序。但實際上呢，外排序的效率比上面提到的方法都低得多，只有在內存實在不夠用的時候才適合考慮（即便在內存不夠用的情況下，我們依然可以利用hash，把大文件劃分成若干個小到內存可以容納為止的文件，分別計算以后在來歸并求最大數(shù)，目的就是要盡量避免外排序帶來的大量磁盤讀寫）。

如果再把思路放寬一點，真的需要統(tǒng)計所有的單詞嗎？其實對于一篇文章來說，其中的內容都是有文字意義的，換言之，只有很少的單詞可能成為“重復最多”的，這個數(shù)量應該是非常非常有限的。比如在遇到一個“is”的時候，我們知道要把它列入統(tǒng)計范疇，但是遇到“distribution”這樣的詞呢，大可跳過。

還可以找得到很多這樣的榔頭，比如概率公式，C(m,n)和A(m,n)，即組合數(shù)和排列數(shù)，對于某些概率、混合、排列的問題就用它來套；再比如常見的榔頭——動態(tài)規(guī)劃，學了以后看到求最優(yōu)解問題就很想用DP來解；還有在數(shù)據(jù)量很大的情況下利用hash、區(qū)域劃分等等“分而治之”的化簡思想……但是，這些都是常規(guī)思路，就如同Top K問題用堆排序來求解，尋找“不出現(xiàn)”的單詞就使用bit map，“不重復出現(xiàn)”的單詞就使用2-bit map等等這樣的問題一樣，終歸是簡單粗暴那一類的。即便解決了問題，也沒有給人眼前一亮的“巧妙”的感覺。

跳出算法，在很多工程問題上也有類似的體會。記得以前在做一個項目的單元測試，Easy Mock + Easy Mock Extension + Power Mock，這樣一套庫，mock的能力實在強大，幾乎沒有測試不了的代碼了，于是就拿了這把榔頭到處砸，卻忘了單元測試的最終目的是什么，那一些代碼是值得做單元測試的。后來利用ant給測試環(huán)境中，不關心邏輯的那一層，使用自己寫的樁代碼mock掉，并且去掉了好多價值不大的測試代碼（在代碼更新的時候測試代碼需要同步維護，這個成本不劃算，所以我們把一些價值有但不大的單元測試用例合并或者刪除了），層次反而更清楚，測試代碼反而更易懂了。

前些日子和我們組的數(shù)學達人討論問題的時候他說，我們最常見的最通用的榔頭，主要還是在“解空間的搜索”和“解的構造”這兩方面。如果能構造，復雜程度往往就要低于搜索，這是一個遞進；而另一方面，任何一個實際問題都是有額外信息的，通用的榔頭卻是不考慮這些實際信息的，就像這個求重復次數(shù)最多的單詞問題一樣，文件有多大、文件內存放的是一篇實際有意義的文章，等等（再比如如果這個文件里面不是一億個單詞，而是一億個整數(shù)呢），這些都是額外的信息，這是另一個遞進。利用這些，簡化了問題，就可以殺雞不用牛刀了吧。

文章未經特殊標明皆為本人原創(chuàng)，未經許可不得用于任何商業(yè)用途，轉載請保持完整性并注明來源鏈接《四火的嘮叨》

你可能也喜歡：

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com