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实现以时间换空间的缓存替换算法，希望对大家有所帮助！
相关推荐
-
使用python删除nginx缓存文件示例(python文件操作)
调用时输入参数如: www.jb51.net/表示删除www.jb51.net首页的缓存, www.jb51.net/test.php就表示删除/test.php的缓存 复制代码 代码如下: #coding=utf8import sys,osimport hashlibif len(sys.argv)<2: print("你没有输入地址.") sys.exit()path="/home/cache"#缓存目录md5v = hashlib.md5(
-
python中stdout输出不缓存的设置方法
考虑以下python程序: 复制代码 代码如下: #!/usr/bin/env python import sys sys.stdout.write("stdout1 ")sys.stderr.write("stderr1 ")sys.stdout.write("stdout2 ")sys.stderr.write("stderr2 ") 其中的sys.stdout.write也可以换成print.运行这程序,你觉得会输出什么
-
Python实现以时间换空间的缓存替换算法
缓存是指可以进行高速数据交换的存储器,它先于内存与CPU交换数据,因此速度很快.缓存就是把一些数据暂时存放于某些地方,可能是内存,也有可能硬盘. 在使用Scrapy爬网站的时候,产生出来的附加产物,因为在Scrapy爬取的时候,CPU的运行时间紧迫度不高(访问频次太高容易被封禁),借此机会难得来上一下,让自己的内存解放一下. 算法原理: 通过将要缓存的数据用二进制展开,得到的二进制数据映射到缓存字段上,要检验是否已经缓存过,仅需要去查找对应的映射位置即可,如果全部匹配上,则已经缓存. # 二进制
-
如何使用Python对NetCDF数据做空间相关分析
引言:我一直想理解空间相关分析的计算思维,于是今天又拿起Python脚本和数据来做练习.首先需要说明的是,这次实验的数据和Python脚本均来自于[好久不见]大佬,在跟大佬说明之后,允许我写到公众号来与大家共享,在此对大佬的指点表示感谢,这次实验的脚本可在气象家园或简书app(如果没记错的话)搜索到这次实验的相关内容,也可以微信或者后台发消息给我获取.在此之前我觉得自己还没理解这个方法的计算思维,检验的标准就是我能否迅速运用到其他方面.于是今天又重新回来温习一遍,我把自己的理解与大伙共同交流.
-
Python基础教程之名称空间以及作用域
目录 前言 名称空间 什么是名称空间 名称空间的意义 名称空间的查找顺序 局部名称空间详解 嵌套函数中的查找顺序 关于嵌套函数的使用 作用域 什么是作用域 global语句 nonlocal语句 题目题目 小结 总结 前言 所谓“基础不狠,人站不稳”,对于任何一种编程语言来说基础往往都是重中之重,以Python为例,其中的两大分水岭就是函数编程和面向对象,而今天所要巩固的知识点后续会多次使用,那就是名称空间和作用域 名称空间 什么是名称空间 在Python中名称空间是用存储对象和名字绑定关系的地
-
python opencv实现证件照换底功能
本文实例为大家分享了python opencv实现证件照换底功能的具体代码,供大家参考,具体内容如下 思路:先转到HSV空间,利用颜色提取背景制作掩模版mask,然后通过按位操作提取人像和制作新背景,最后叠加背景和人像得到换底后照片 代码 #-*-coding:utf-8-*- import cv2 import numpy as np def cvtBackground(path,color): """ 功能:给证件照更换背景色(常用背景色红.白.蓝) 输入参数:path:
-
详解Python小数据池和代码块缓存机制
前言 本文除"总结"外,其余均为认识过程:3.7.5:这部分官方文档不知道在哪里找,目前没有找到,有谁知道的可以麻烦留言吗? 谢谢了! 总结: 如果在同一代码块下,则采用同一代码块下的缓存机制: 如果是不同代码块,则采用小数据池的驻留机制: 需要注意的是,交互式输入时,每个命令都是一个代码块: 实现 Intern 保留机制的方式非常简单,就是通过维护一个字符串储蓄池,这个池子是一个字典结构,编译时,如果字符串已经存在于池子中就不再去创建新的字符串,直接返回之前创建好的字符串对象, 如果
-
Python Barbershop实现照片换发型功能
目录 前言 环境部署 1.导入environment/environment.yaml环境 2.安装pytorch 3.依赖库安装 4. cl.exe环境变量配置 5.模型下载 6.发型数据下载 7.代码调整 项目验证 1.预处理照片 2.换发型 总结 前言 最近看到一个开源项目(Barbershop),可以将照片中的发型更换成另一个,很神奇.先给大家看看项目给出的效果图. 先说说我在安装使用该项目的感受,因为作者给的安装说明太少,我边看代码边安装环境花了整整8个小时,顺便还在等安装的过程中,追
-
基于Python实现丝滑换装视频剪辑
目录 软硬件.技能需求 颜色变换说明 Python 应用插件 思路流程 MiVOS 模块交互式 看到人家用PR什么编辑软件做这种丝滑一键换装的视频,自己也想尝试一下.不过PR这破玩意太难用了,还不如敲代码来的省事. 最开始想用 moviepy 的 moviepy.video.fx.all.mask_color 蒙版处理,发现还要结合目标识别这个复杂度就有点上头了.然后换了一个思路进行处理之后就算成功了吧.来看看成品效果先. python 丝滑换衣算法演示 还是老套路先说机器配置,机器配置不够的玩
-
Python使用当前时间、随机数产生一个唯一数字的方法
本文实例讲述了Python使用当前时间.随机数产生一个唯一数字的方法.分享给大家供大家参考,具体如下: Python生成当前时间很简单,比Java的代码简短多了,Java产生时间可参考<Java获取当前系统事件System.currentTimeMillis()方法> 具体代码如下: #-*-coding:utf-8-*- import datetime now = datetime.datetime.now().strftime("%Y-%m-%d %H:%M:%S")
-
python获得文件创建时间和修改时间的方法
本文实例讲述了python获得文件创建时间和修改时间的方法.分享给大家供大家参考.具体如下: 这里需要用户从控制台输入文件路径 import os.path, time import exceptions class TypeError (Exception): pass if __name__ == '__main__': if (len(os.sys.argv) < 1): raise TypeError() else: print "os.sys.argv[0]: %s"
-
分享一下Python 开发者节省时间的10个方法
Python 是一个美丽的语言,可以激发用户对它的爱.所以如果你试图加入程序员行列,或者你有点厌倦C++,Perl,Java 和其他语言,我推荐你尝试Python. Python有很多吸引程序员的功能 ,它易学,面向对象,字节码编译,免费且开源.还有运行时检查.完整快速的支持,可以执行各种任务的扩展. 高效的Python 在这篇文章,我想强调一些 Python 可以节约时间并最大限度地提高生产力的方面.在做准备时,我咨询了几个 Pythonists,他们最节省时间的技巧是什么?答案在这里...