BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

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

| 作者 郑柯 关注 3 他的粉丝 发布于 2012年3月19日. 估计阅读时间: 3 分钟 | Google、Facebook、Pinterest、阿里、腾讯 等顶尖技术团队的上百个可供参考的架构实例!

布隆过滤与多路归并

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

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

采用先垂直切分然后比较的方法 by Z Joe

去年在做过类似的系统,如下:
1.通常情况下,时间复杂度将是50亿*50亿=2.5*10^21,空间复杂度2*50亿*64bytes
2.不失一般性,假设URL格式形如 www.XXX.com/Y
3.根据URL中Y值的不同,分别将A,B中的URL划分为0~999,1000个集合(或者500个,或者900个集合也行,根据实际情况而定)
4. 分别将集合Ai与Bi进行比较,比较的算法可以用Hash,也可以用归并排序,等等,找出相同的URL即可。
5. 时间复杂度=1000*(50亿/1000)*(50亿/1000)=2.5*10^18, 空间复杂度降为2*50亿/1000*64=6.4亿bytes
即可以在单机情况下完成

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

1 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT