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

给我一把榔头,满世界都是钉子 一篇文章存成一个巨大的文件,总共大约有一亿个单词,要找出里面重复次数最多的。怎么做?

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

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

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

分享到:

One comment

  1. 匿名 说道:

    《暗时间》152页,“锤子和钉子”

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: