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

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

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

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

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

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

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

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

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

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

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

你可能也喜歡：

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