关于“消重”问题的解决,从管道到并行
消重,简单说就是把一个序列中重复的元素消除掉,输出的结果中每个元素都是唯一的。比如:
[1,2,1,3,2] 经过消重后,结果是: [1,2,3]
看上去这个问题好像非常简单无聊,但是实际工作中却经常能遇到,比如对web访问日志的来源ip ,或者访问页面进行消重统计,等等。
今天在一个Python讨论群里面,有个人提了一个问题: 有上亿甚至几十亿个的数字,如何得到消重后的列表?
正好,就着这个实际问题,来看一下一个看似简单的问题, 在数据量极大的情况下,会引出什么有趣的东西来。
(注:这里面对算法数据规模,只是一个大体上的估计,我没时间做具体的性能测试,只为了表明解决方法)
===
首先,最简单的算法,对于几百,甚至几万行数据量的情况下,很简单:
1. 使用 set ,通过列表创建一个set,就可以得到不重复的元素来。 够简单吧:
>>> s = [1,2,1,2,3,1] >>> list(set(s)) [1, 2, 3]
数量再大点, 可以用数据库来帮助我们, sql 里面有 distinct 语句,因此很简单:
select distinct(field) from some_table;
这个能处理的数据量依系统的能力,以及数据库的能力而定。用数据库能解决上面那个网友的问题么? 也许是可以的,几亿到几十亿,导入到数据库的表中,或者加上一些分表达技巧,应该能搞定。 但是这样是不是太兴师动众了呢。
喜欢在Unix命令行下面解决问题的众位,马上就会想到 sort | uniq , Unix的管道就是其精神的精髓啊。我们经常会写这类的命令:
cat access.log | cut -f1 | sort | uniq -c
这个很简单了,就是把一个web日志里面每一行的第一列(时间或是ip)取出来(cut), sort 一下把相同的ip放在一起, 然后 uniq -c 一下将每个ip 出现的次数统计一下, 最后的结果就是类似于:
102 192.168.xx.xxx
82 192.168.xx.xx
.....
但是这个命令中的瓶颈,就在 sort 上了, 排序一个几百M 的文件明显会感到很慢。直接这样处理几十G 的数据文件显然不现实。
怎么办?分了它呗。
1. 切分原始输入数据,根据每个数字所属的范围,分割到不同的文件中
2. 对每个小文件, 用 sort | uniq 消重
3. 把上面生成的结果合并起来,就是最终的结果。
so easy吧
上面的3个步骤,分别就对应着上图中的几个箭头。这里也不卖官司了,直说了吧,这就是 MapReduce 算法。
在 Map阶段,每个小文件进行消重操作的时候,是与其他的文件没有关系的,因此可以独立的分布到不同的机器上去计算。这就是很简单的分布式计算的应用。
有一些很成熟的MapReduce 框架可以帮我们来做,比如 Hadoop , 不过呢,这个跟数据库一样,也是比较兴师动众的。如果你有兴趣,并且有多台机器,经常需要做这类大数据处理的话,还是学习下 hadoop 的好。
如果只是临时任务,不想学习Hadoop那些框架, 可以自己山寨一下,用个脚本,把输入文件分割成小文件, 然后 scp 到不同的机器上,在每个机器跑 sort | uniq ,然后再把文件 scp 到一台机器,用 cat 合并成一个最终结果。 ok,搞定。
最后总结一句, Unix 的管道,与 FP 中函数串接计算的方式,是非常相似的,他们的思想相通。而 FP 的一个特点是方便进行并行扩展。这个小例子很好的展现了这一点。老兵不死,Unix管道精神不朽哈。