Python实现以时间换空间的缓存替换算法

缓存是指可以进行高速数据交换的存储器，它先于内存与CPU交换数据，因此速度很快。缓存就是把一些数据暂时存放于某些地方，可能是内存，也有可能硬盘。

在使用Scrapy爬网站的时候，产生出来的附加产物，因为在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

实际使用效果如何呢?

在和Python默认的 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，非常不建议在大量不定长的数据，而且数据本身比较大的情况下使用

以上内容是小编给大家介绍的Python实现以时间换空间的缓存替换算法，希望对大家有所帮助！