问一个bloom filter 和 bitmap的使用区别 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 问一个bloom filter 和 bitmap的使用区别

相关主题
● T电面，肯定完了！	● T的一道电面题
● 有人面试被问到过bloom filter么	● twitter online test 面筋
● 面试题，大规模url求重复讨论	● 这个最优解应该是怎样的？
● 问个memory limits的题	● 亚经
● 数组里面找数个出现了奇数次的整数,怎么找?	● L家悲剧，发面筋，顺求分析原因
● 弱弱的问下：bit　map 和map 有啥区别	● 讨论两道L家的设计题
● amazon 一道题	● FB type-ahead implementation with bloom filter
● 请问一道面试题	● 面试问bloom filter,reservoir sampling过分么？

相关话题的讨论汇总
话题: bloom话题: filter话题: bitmap话题: url话题: 亿个

进入JobHunting版参与讨论

(共1页)

l*********y
发帖数: 142

我是在看
http://www.mitbbs.com/article/JobHunting/31491461_3.html
bloom filter可以看做是对bit-map的扩展。
我原来的想法是bloom filter要比bit map省空间，因为bloom filter设计的思想就是
用错误率换空间。但是看了那个帖子里的两道题，又迷茫了不少。
问题1：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让
你找出A,B文件共同的URL。
建议答案：根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿
，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差
并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换
成ip，则大大简单了。
问题2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出
现2次及以上。或者我们不用2bit来进行表示，我们用

(共1页)

进入JobHunting版参与讨论

相关主题
● 面试问bloom filter,reservoir sampling过分么？	● 数组里面找数个出现了奇数次的整数,怎么找?
● leetcode被ban掉了	● 弱弱的问下：bit　map 和map 有啥区别
● 设计web services API最需要注意的是什么？	● amazon 一道题
● Bitmap是怎么回事啊？	● 请问一道面试题
● T电面，肯定完了！	● T的一道电面题
● 有人面试被问到过bloom filter么	● twitter online test 面筋
● 面试题，大规模url求重复讨论	● 这个最优解应该是怎样的？
● 问个memory limits的题	● 亚经

相关话题的讨论汇总
话题: bloom话题: filter话题: bitmap话题: url话题: 亿个

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天