2012.3.19 微博热报：布隆过滤与多路归并

  • 郑柯

2012 年 3 月 18 日

话题：语言 & 开发架构

布隆过滤与多路归并

JavaChen发布一条可作为面试题的微博：

给你 A,B 两个文件，各存放 50 亿条 URL，每条 URL 占用 64 字节，内存限制是 4G，让你找出 A,B 文件共同的 URL。如果是三个乃至 n 个文件呢？http://t.cn/zOMmWru

李良普：

bloom filter 可以实现，但是很少使用。

HubbleDotNet：

布隆的关键是随机数的选取要尽可能接近平均分布

kkkua：

BF 只是说有哪些 URL 在以前已出现过了。 优点难度的是真正“找出”n 个 URL 列表中所有那些相同的 URL（聚类问题）。好办法是做一个 incremental index, 边输入边去重，正如高性能的重复网页检测

海纳百通：

我的理解是：1 布隆过滤 是能“激进地”找出“很可能已存在的”URL；2 但是，在发现可能的重复后，要确定并记录下 URL，就要索引到 URL，并做全文比对；3 这个问题里还连带提到“n 个文件”。。。所以，有改进的空间吧？

bnu_chenshuo：

毛估了一下，单机（4G 内存，双硬盘）4 个小时应该能搞定，没用到 bloom filter。

陆鑫 Lucian：

bloom filter 是我能想到速度最快的方法了，这题的关键就是先把要处理的数据总数降低数个量级，剩下的就好办了。陈硕老师能介绍下你的思路，效率如何吗？

matrix-reload：

用 MapReduce 方法吧

bnu_chenshuo回复@陆鑫 Lucian：

你估计用 bloom filter 解决，单机花多少小时？我的思路很简单，分块（1G）排序再多路归并，在归并的同时求集合的交集。

bnu_chenshuo回复@如此玄妙：

多路归并用不着“最后一次归并 将 2 个一样大的已排序的文件合并”。AB 两个文件，分块排成各 300 个 1G 的文件，然后同时打开这一共 600 个文件读数据，两套文件分别多路归并，并求交集，把结果写出来即可。

原题不是要求单机 4G 内存吗？“300 个 1g 文件归并的比较次数 会和比 2 个 150g 文件大很多”是的，但是你那两个 150g 的文件事先要花多长时间生成？“每次取出数据，都需要在一个 300 条记录的树或者堆上进行一次排序”是的，不过这并不影响整体速度，内存处理速度只要高于磁盘读数据的速度即可

摇摆巴赫：

bloom 需要磁盘随机 IO 吧，内存里的 hash bit 相等后还得磁盘读出来看 url 是不是相同，分块排序应该是顺序磁盘 IO，我觉得哪个快要看重复率

@TreapDB：

先把这些 url 算 hash%100, 分别存到 100 个文件夹里，每个文件夹有两个文件，分别来自 A 和 B. 这两个小文件可以在内存中求交集生成小文件。最后，把这些交集小文件 cat 成一个文件。并不要求有序。

今日微博推荐

梁斌 penny

推荐理由：清华大学计算机科学与技术系在读博士；《走进搜索引擎》作者、《深入搜索引擎》译者，THUIRDB的 Coder，个人博客地址：http://blog.csdn.net/pennyliang。

语言 & 开发架构