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

语言 & 开发架构