给我一把榔头，满世界都是钉子

一篇文章存成一个巨大的文件，总共大约有一亿个单词，要找出里面重复次数最多的。怎么做？ Hadoop是一把威力巨大的榔头，在使用过Hadoop之后，看着任何东西都想把它给map reduce了。有一个关于Jeff Dean的小笑话，说在睡不着觉的时候，一般人是数羊，Jeff De

一篇文章存成一个巨大的文件，总共大约有一亿个单词，要找出里面重复次数最多的。怎么做？

Hadoop是一把威力巨大的榔头，在使用过Hadoop之后，看着任何东西都想把它给map reduce了。有一个关于Jeff Dean的小笑话，说在睡不着觉的时候，一般人是数羊，Jeff Dean是map reduce他的羊群。所以，我的办法是，把这个文件拆分成若干个小文件，在map过程用hash算法保证相同的单词落入一个文件（这点很重要），计算单词出现次数，在reduce过程取得重复次数最多的单词来。

但是，真有必要这样啰嗦吗？

只有一亿个单词，简单估算一下，一个字母占据两个字节，假设单词平均长度5，即便是最极端情况，这些单词里面没有重复，单词本身也就消耗1G而已；而实际上一篇文章单词的重复率是非常高的，这个数据量完全可以放在内存里面计算。还没完，不一定非得要用Hash，如果借由Trie树，可以节点压缩，占用更少的空间。

这只是一个用榔头来敲钉子的一个小例子而已，在我刚学算法的时候，那时候刚接触外排序，这样的问题我或许会第一反应使用外排序来做，在那个时候，这把榔头就是外排序。但实际上呢，外排序的效率比上面提到的方法都低得多，只有在内存实在不够用的时候才适合考虑（即便在内存不够用的情况下，我们依然可以利用hash，把大文件划分成若干个小到内存可以容纳为止的文件，分别计算以后在来归并求最大数，目的就是要尽量避免外排序带来的大量磁盘读写）。

如果再把思路放宽一点，真的需要统计所有的单词吗？其实对于一篇文章来说，其中的内容都是有文字意义的，换言之，只有很少的单词可能成为“重复最多”的，这个数量应该是非常非常有限的。比如在遇到一个“is”的时候，我们知道要把它列入统计范畴，但是遇到“distribution”这样的词呢，大可跳过。

还可以找得到很多这样的榔头，比如概率公式，C(m,n)和A(m,n)，即组合数和排列数，对于某些概率、混合、排列的问题就用它来套；再比如常见的榔头——动态规划，学了以后看到求最优解问题就很想用DP来解；还有在数据量很大的情况下利用hash、区域划分等等“分而治之”的化简思想……但是，这些都是常规思路，就如同Top K问题用堆排序来求解，寻找“不出现”的单词就使用bit map，“不重复出现”的单词就使用2-bit map等等这样的问题一样，终归是简单粗暴那一类的。即便解决了问题，也没有给人眼前一亮的“巧妙”的感觉。

跳出算法，在很多工程问题上也有类似的体会。记得以前在做一个项目的单元测试，Easy Mock + Easy Mock Extension + Power Mock，这样一套库，mock的能力实在强大，几乎没有测试不了的代码了，于是就拿了这把榔头到处砸，却忘了单元测试的最终目的是什么，那一些代码是值得做单元测试的。后来利用ant给测试环境中，不关心逻辑的那一层，使用自己写的桩代码mock掉，并且去掉了好多价值不大的测试代码（在代码更新的时候测试代码需要同步维护，这个成本不划算，所以我们把一些价值有但不大的单元测试用例合并或者删除了），层次反而更清楚，测试代码反而更易懂了。

前些日子和我们组的数学达人讨论问题的时候他说，我们最常见的最通用的榔头，主要还是在“解空间的搜索”和“解的构造”这两方面。如果能构造，复杂程度往往就要低于搜索，这是一个递进；而另一方面，任何一个实际问题都是有额外信息的，通用的榔头却是不考虑这些实际信息的，就像这个求重复次数最多的单词问题一样，文件有多大、文件内存放的是一篇实际有意义的文章，等等（再比如如果这个文件里面不是一亿个单词，而是一亿个整数呢），这些都是额外的信息，这是另一个递进。利用这些，简化了问题，就可以杀鸡不用牛刀了吧。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接《四火的唠叨》

你可能也喜欢：