AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

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

  • 2012-03-18
  • 本文字数:1071 字

    阅读完需:约 4 分钟

布隆过滤与多路归并

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

2012-03-18 20:492436
用户头像

发布了 479 篇内容, 共 172.1 次阅读, 收获喜欢 52 次。

关注

评论

发布
暂无评论
发现更多内容

Linux一学就会之Centos8软件包的管理和安装之yum管理软件包

学神来啦

Linux centos 运维 rpm yum

Python代码阅读(第67篇):获取列表中的去重后的元素

Felix

Python 编程 列表 阅读代码 Python初学者

偷天换日,用JavaAgent欺骗你的JVM

码农参上

字节码插桩 代理 探针 签约计划第二季

热门Scrum敏捷看板工具

顿顿顿

项目管理 Scrum 敏捷开发 研发管理 产品研发

安全攻防实战系列MSF

网络安全学海

网络安全 信息安全 渗透测试 WEB安全 安全漏洞

一文讲透数仓临时表的用法

华为云开发者联盟

数据库 sql Local GaussDB(DWS) 临时表

基于HTML、CSS、JS的小游戏/工具制作过程及完整源码

海拥(haiyong.site)

28天写作 内容合集 签约计划第二季 12月日更 技术专题合集

春松客服入驻Rainbond开源应用商店

北京好雨科技有限公司

2021商业评论管理行动力峰会

大咖说

商业 直播

为什么要做团建TB?(6/28)

赵新龙

28天写作

使用Harbor作为Rainbond默认容器镜像仓库,扩展Rainbond镜像管理能力

北京好雨科技有限公司

目前市面上堡垒机的品牌有哪些?采购时候需要考虑哪些?

行云管家

网络安全 等保 堡垒机 等级保护

蒙娜丽莎Rap的秘密!这个AI算法绝不能错过!!!

百度开发者中心

AI

企业如何做好员工安全意识提升

腾讯安全云鼎实验室

会用泛型,但你知道什么是泛型的类型擦除吗?

码农参上

Java泛型 签约计划第二季

Smack库 XMPP Tigase异常SASLErrorException

Changing Lin

12月日更

【混合云】部分混合云管理平台大汇总

行云管家

云计算 公有云 混合云 云管平台

弹性伸缩 && 多机房

空空

架构设计

微服务

空空

架构设计

【讲坛实录】知识图谱的探索与应用

星环科技

知识图谱

ipvs localhost 为何不正常

Geek_f24c45

k8s IPVS kube-proxy

单库单应用 && 内容分发

空空

架构设计

查询分离

空空

架构设计

编译优化后,for循环中i++和++i究竟哪个效率高?

码农参上

字节码 编译优化 签约计划第二季

网易应用创新开发者大赛成功在杭举办,十强队伍现场比拼

网易云信

人工智能 音视频 直播

Redis 的事务支持 ACID 么?

码哥字节

redis 事务 ACID 签约计划第二季

换个角度思考勒索攻击事件

华为云开发者联盟

漏洞 勒索 攻击 安全检测 蜜罐检测

和合共赢,DataPipeline与麒麟软件完成产品兼容性互认证

DataPipeline数见科技

中间件 数据库中间件

浅谈Java编译优化之常量折叠技术

码农参上

编译器优化 签约计划第二季

多级缓存 && 分库分表

空空

架构设计

动图图解GC算法 - 让垃圾回收动起来!

码农参上

垃圾回收 垃圾回收算法 签约计划第二季

2012.3.19微博热报:布隆过滤与多路归并_语言 & 开发_郑柯_InfoQ精选文章