Python实现以时间换空间的缓存替换算法
缓存是指可以进行高速数据交换的存储器,它先于内存与CPU交换数据,因此速度很快。缓存就是把一些数据暂时存放于某些地方,可能是内存,也有可能硬盘。
在使用Scrapy爬网站的时候,产生出来的附加产物,因为在Scrapy爬取的时候,CPU的运行时间紧迫度不高(访问频次太高容易被封禁),借此机会难得来上一下,让自己的内存解放一下。
算法原理:
通过将要缓存的数据用二进制展开,得到的二进制数据映射到缓存字段上,要检验是否已经缓存过,仅需要去查找对应的映射位置即可,如果全部匹配上,则已经缓存。
#二进制就是个二叉树
#如下面可以表示出来的数据有0,1,2,3四个(两个树独立)
01
/\/\
0101
因此对缓存的操作就转化为对二叉树的操作,添加和查找只要在二叉树上找到对应路径的node即可。
算法关键代码:
def_read_bit(self,data,position): return(data>>position)&0x1 def_write_bit(self,data,position,value): returndata|value<<position
实际使用效果如何呢?
在和Python默认的set相比较,得出测试结果如下(存取整型,不定长字符串,定长字符串):
Pleaseselecttestmode:4 Pleaseentertesttimes:1000 ==================================================================================================== TESTRESULT:: ==================================================================================================== set()bytecache items10001000 add(s)0.00.0209999084473 read(s)0.00.0149998664856 hits10001000 missed00 size3299256 add(s/item)0.02.09999084473e-05 read(s/item)0.02.09999084473e-05 ==================================================================================================== size(set/bytecache):589.142857143 addtime(bytecache/set):N/A readtime(bytecache/set):N/A ==================================================================================================== ...testfixedlength&intdataend... ==================================================================================================== TESTRESULT:: ==================================================================================================== set()bytecache items10001000 add(s)0.001000165939336.1740000248 read(s)0.07.21300005913 hits999999 missed00 size3299256 add(s/item)1.00016593933e-060.0061740000248 read(s/item)0.00.0061740000248 ==================================================================================================== size(set/bytecache):589.142857143 addtime(bytecache/set):6172.97568534 readtime(bytecache/set):N/A ==================================================================================================== ...testmutativelength&stringdataend... ==================================================================================================== TESTRESULT:: ==================================================================================================== set()bytecache items10001000 add(s)0.00.513999938965 read(s)0.00.421000003815 hits999999 missed00 size3299256 add(s/item)0.00.000513999938965 read(s/item)0.00.000513999938965 ==================================================================================================== size(set/bytecache):589.142857143 addtime(bytecache/set):N/A readtime(bytecache/set):N/A ==================================================================================================== ...testFixedlength(64)&stringdataend...
测试下来,内存消耗控制的比较好,一直在56字节,而是用set的内存虽然也不是很大,当相较于ByteCache来说,则大上很多。
但ByteCache的方式来缓存,最大的问题是当碰到非常大的随机数据时,消耗时间会比较惊人。如下面这种随机长度的字符串缓存测试结果:
Pleaseselecttestmode:2 Pleaseentertesttimes:2000 ==================================================================================================== TESTRESULT:: ==================================================================================================== set()bytecache items20002000 add(s)0.0040001869201731.3759999275 read(s)0.044.251999855 hits19991999 missed00 size13129656 add(s/item)2.00009346008e-060.0156879999638 read(s/item)0.00.0156879999638 ==================================================================================================== size(set/bytecache):2344.57142857 addtime(bytecache/set):7843.63344856 readtime(bytecache/set):N/A ==================================================================================================== ...testmutativelength&stringdataend...
在2000个数据中,添加消耗31s,查找消耗44s,而set接近于0,单条数据也需要16ms(均值)才能完成读/写操作。
不过,正如开头说的,在紧迫度不是很高的Scrapy中,这个时间并不会太过于窘迫,更何况在Scrapy中,一般是用来缓存哈希后的数据,这些数据的一个重要特性是定长,定长在本缓存算法中还是表现不错的,在64位长度的时候,均值才0.5ms。而与此同时倒是能在大量缓存的时候,释放出比较客观的内存。
如果有更好的缓存算法能让速度在上新台阶,也是无比期待的。。。
总结:
1.此方法的目标是用时间换取空间,切勿在时间紧迫度高的地方使用
2.非常适用于大量定长,且数据本身比较小的情况下使用
3.接2,非常不建议在大量不定长的数据,而且数据本身比较大的情况下使用
以上内容是小编给大家介绍的Python实现以时间换空间的缓存替换算法,希望对大家有所帮助!