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

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

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 掉，并且去掉了好多价值不大的测试代码（在代码更新的时候测试代码需要同步维护，这个成本不划算，所以我们把一些价值有但不大的单元测试用例合并或者删除了），层次反而更清楚，测试代码反而更易懂了。

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

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