欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-11 12:07:44
...

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

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

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

文章系本人原创,转载请保持完整性并注明出自《四火的唠叨》