这边的爬虫系统又出现了一些个瓶颈。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。一开始我们首先排除掉了set集合，虽然set集合比数组类型的list。但是内存占用的大小，和几十亿条数据对比的时候，还是很出现性能的瓶颈 。 

这个时候大家可以用bitmap和bloomfilter来做高效的处理。 bitmap 其实和bloomfilter很像，但是他的冲突率要比bloomfilter要高 。 

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。

bloomfilter和bitmap都不能做删除的， 你要是有删除的需求，可以用bloomfilter的加强版，cbf    ~

[root@vm55 ~]# ipython
Python 2.6.6 (r266:84292, Jan 22 2014, 09:42:36)
Type "copyright", "credits" or "license" for more information.

IPython 0.13.2 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: from pybloom import BloomFilter

In [2]: f = BloomFilter(capacity=1000, error_rate=0.001)

In [3]: [f.add(x) for x in range(10)]
Out[3]: [False, False, False, False, False, False, False, False, False, False]

In [4]: all([(x in f) for x in range(10)])
Out[4]: True

In [5]: 10 in f
Out[5]: False

In [6]: 11 in f
Out[6]: False

In [7]: 1 in f
Out[7]: True

In [8]: f.capacity
Out[8]: 1000

我们现在已经把bloomfilter用上了，性能上和内存消耗上有长足的进步。 

---

大家觉得文章对你有些作用！ 如果想赏钱，可以用微信扫描下面的二维码，感谢!
另外再次标注博客原地址  xiaorui.cc