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 的大作中提到】
: 我是在看
: 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 的大作中提到】
: 你如果用第二题解法 则要求使用的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太难弄了 特别规模大
|
|
