问一个bloom filter 和 bitmap的使用区别# JobHunting - 待字闺中
l*y
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来进行表示,我们用
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来进行表示,我们用