l*********y 发帖数: 142 | 1 我是在看
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来进行表示,我们用 | a****9 发帖数: 418 | 2 你如果用第二题解法 则要求使用的Hash是perfect Hash
也就是对50亿个元素hash以后没有collision
(注意在第二题当中, 这个perfect hash是自然满足的,
第i个数就对应第i个entry.
但在你这里就不能这样,url不是自然有序的,
当然你可以用tire来排序,trie也是一种可以用来hash的方式了)
其实关于BloomFilter的paper里也提到
使用Perfect Hash+fingerprint是可以达到information theoretic bound的
就是这个perfect hash太难弄了 特别规模大
【在 l*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我是在看 : 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是一一对应的,就可以转换
| l*********y 发帖数: 142 | 3 非常感谢。很清楚了。
【在 a****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你如果用第二题解法 则要求使用的Hash是perfect Hash : 也就是对50亿个元素hash以后没有collision : (注意在第二题当中, 这个perfect hash是自然满足的, : 第i个数就对应第i个entry. : 但在你这里就不能这样,url不是自然有序的, : 当然你可以用tire来排序,trie也是一种可以用来hash的方式了) : 其实关于BloomFilter的paper里也提到 : 使用Perfect Hash+fingerprint是可以达到information theoretic bound的 : 就是这个perfect hash太难弄了 特别规模大
|
|