用时间换空间的缓存算法

在使用Scrapy爬网站的时候,产生出来的附加产物,因为在爬取的时候,CPU的运行时间紧迫度不高(访问频次太高容易被封禁),借此机会难得来上一下,让自己的内存解放一下。

算法原理:

通过将要缓存的数据用二进制展开,得到的二进制数据映射到缓存字段上,要检验是否已经缓存过,仅需要去查找对应的映射位置即可,如果全部匹配上,则已经缓存。

# 二进制就是个二叉树
# 如下面可以表示出来的数据有0, 1, 2, 3四个(两个树独立)

  0      1
 / \    / \
0   1  0   1

因此对缓存的操作就转化为对二叉树的操作,添加和查找只要在二叉树上找到对应路径的node即可。

 

关键代码:

    def _read_bit(self, data, position):
        return (data >> position) & 0x1

    def _write_bit(self, data, position, value):
        return data | value << position

 

实际使用效果如何呢?

在和默认的set相比较,得出测试结果如下(存取整型,不定长字符串,定长字符串):

Please select test mode:4
Please enter test times:1000
====================================================================================================
TEST RESULT::
====================================================================================================
                    set()                                   bytecache
items               1000                                    1000
add(s)              0.0                                     0.0209999084473
read(s)             0.0                                     0.0149998664856
hits                1000                                    1000
missed              0                                       0
size                32992                                   56
add(s/item)         0.0                                     2.09999084473e-05
read(s/item)        0.0                                     2.09999084473e-05
====================================================================================================
size (set / bytecache): 589.142857143
add time (bytecache / set): N/A
read time (bytecache / set): N/A
====================================================================================================
...test fixed length & int data end...

====================================================================================================
TEST RESULT::
====================================================================================================
                    set()                                   bytecache
items               1000                                    1000
add(s)              0.00100016593933                        6.1740000248
read(s)             0.0                                     7.21300005913
hits                999                                     999
missed              0                                       0
size                32992                                   56
add(s/item)         1.00016593933e-06                       0.0061740000248
read(s/item)        0.0                                     0.0061740000248
====================================================================================================
size (set / bytecache): 589.142857143
add time (bytecache / set): 6172.97568534
read time (bytecache / set):  N/A
====================================================================================================
...test mutative length & string data end...

====================================================================================================
TEST RESULT::
====================================================================================================
                    set()                                   bytecache
items               1000                                    1000
add(s)              0.0                                     0.513999938965
read(s)             0.0                                     0.421000003815
hits                999                                     999
missed              0                                       0
size                32992                                   56
add(s/item)         0.0                                     0.000513999938965
read(s/item)        0.0                                     0.000513999938965
====================================================================================================
size (set / bytecache): 589.142857143
add time (bytecache / set):  N/A
read time (bytecache / set):  N/A
====================================================================================================
...test Fixed length(64) & string data end...

测试下来,内存消耗控制的比较好,一直在56字节,而是用set的内存虽然也不是很大,当相较于ByteCache来说,则大上很多。

ByteCache的方式来缓存,最大的问题是当碰到非常大的随机数据时,消耗时间会比较惊人。如下面这种随机长度的字符串缓存测试结果:

Please select test mode:2
Please enter test times:2000
====================================================================================================
TEST RESULT::
====================================================================================================
                    set()                                   bytecache
items               2000                                    2000
add(s)              0.00400018692017                        31.3759999275
read(s)             0.0                                     44.251999855
hits                1999                                    1999
missed              0                                       0
size                131296                                  56
add(s/item)         2.00009346008e-06                       0.0156879999638
read(s/item)        0.0                                     0.0156879999638
====================================================================================================
size (set / bytecache): 2344.57142857
add time (bytecache / set): 7843.63344856
read time (bytecache / set):  N/A
====================================================================================================
...test mutative length & string data end...

 在2000个数据中,添加消耗31s,查找消耗44s,而set接近于0,单条数据也需要16ms(均值)才能完成读/写操作。

 

不过,正如开头说的,在紧迫度不是很高的Scrapy中,这个时间并不会太过于窘迫,更何况在Scrapy中,一般是用来缓存哈希后的数据,这些数据的一个重要特性是定长,定长在本缓存算法中还是表现不错的,在64位长度的时候,均值才0.5ms。而与此同时倒是能在大量缓存的时候,释放出比较客观的内存。

如果有更好的能让速度在上新台阶,也是无比期待的。。。

 

总结:

1. 此方法的目标是用时间换取空间,切勿在时间紧迫度高的地方使用

2. 非常适用于大量定长,且数据本身比较小的情况下使用

3. 接2,非常不建议在大量不定长的数据,而且数据本身比较大的情况下使用

Thursday, February 18, 2016 | 其他技术 编程语言

文章评论

No comments posted yet.

发表评论

Please add 1 and 3 and type the answer here:

关于博主

  一枚成分复杂的网络IT分子,属于互联网行业分类中的杂牌军。