Python实现以时间换空间的缓存替换算法
作者:mrr 发布时间:2021-03-31 13:45:16
缓存是指可以进行高速数据交换的存储器,它先于内存与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实现以时间换空间的缓存替换算法,希望对大家有所帮助!
猜你喜欢
- 长期以来一直以为iframe跟div一样都是块级元素,直到今天在一个群中看到一位朋友问到iframe怎么居中的时候,测试了下发现原来我一直对
- 导语日常开发中,定位程序异常,追溯事件发生场景都需要通过日志记录的方式。可以说一个好的开发日志设计可以让开发人员在后续项目维护的过程中节省时
- 编者按,网站中让人惊喜的往往是那一点细节,只要用心留意你将发现那些美好的用户体验就在身边。新蛋网想自主控制链接在原窗口还是新窗口中打开?看看
- 今天调试某页面样式,发现chrome下出现问题,但是同样基于webkit引擎的safari没有问题,很是郁闷。于是寻找针对google ch
- JavaScript中indexOf函数方法是返回 String 对象内第一次出现子字符串的字符位置。使用方法:strObj.indexOf
- 本文实例讲述了Python 异常的捕获、异常的传递与主动抛出异常操作。分享给大家供大家参考,具体如下:异常的捕获demo.py(异常的捕获)
- 这篇文章主要介绍了Python统计时间内的并发数代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 在Python3环境下,调试实现了《大话设计模式》中简单工厂模式,通过定义单独的工厂类,完成对具体的产品的实例化,参考链接具体实现见代码:#
- 在NumPy中,所有的标准三角函数如sin、cos、tan等均有对应的通用函数。一、利萨茹曲线(Lissajous curve)利萨茹曲线是
- 本文实例讲述了Golang算法问题之整数拆分实现方法。分享给大家供大家参考,具体如下:一个整数总可以拆分为2的幂的和,例如:7=1+2+47
- 本文跟大家谈谈为什么要学python以及如何学好python。一、作为初学者,应该如何学python?很多人对python缩进试的简洁表达不
- display text in large ASCII art fonts 显示大ASCII艺术字体这种东西在源码声明或者软件初始化控制台打
- 一、Pythont如何打开 txt 格式的文件?1.首先我使用pycharm创建一个项目,然后在这个项目里面再创建一个python的包,然后
- Python“json.decoder.JSONDecodeError: Expecting value: line 1
- 这个类可以用来搜索在给定的文本目录中的文件。 它可以给定目录遍历递归查找某些文件扩展名的文件。 并打开找到的文件,并检查他们是否包含搜索词语
- 一、前言:在经过一段时间的存储过程开发之后,写下了一些开发时候的小结和经验与大家共享,希望对大家有益,主要是针对Sybase和SQL Ser
- 对于 link 元素 和 style 元素 我相信大家都比较了解,但对于他们的出现位置可能有误解。在 淘宝 的所有频道中出现这样一个问题:频
- 前2种方法主要用到了列表解析,性能稍差,而最后一种使用的时候生成器表达式,相比列表解析,更省内存列表解析和生成器表达式很相似:列表解析[ex
- 本文实例讲述了thinkPHP框架实现类似java过滤器的简单方法。分享给大家供大家参考,具体如下:写java web代码的时候,可以定义过
- 本文实例讲述了php购物车实现方法。分享给大家供大家参考。具体分析如下:这里我们为你提供个简单的php购物车代码,从增加购物产品与发生购买了