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实现以时间换空间的缓存替换算法，希望对大家有所帮助！
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1359
52
How to solve the permissions problem encountered when viewing Python version in Linux terminal?
Apr 01, 2025 pm 05:09 PM
Solution to permission issues when viewing Python version in Linux terminal When you try to view Python version in Linux terminal, enter python...
How Do I Use Beautiful Soup to Parse HTML?
Mar 10, 2025 pm 06:54 PM
This article explains how to use Beautiful Soup, a Python library, to parse HTML. It details common methods like find(), find_all(), select(), and get_text() for data extraction, handling of diverse HTML structures and errors, and alternatives (Sel
Serialization and Deserialization of Python Objects: Part 1
Mar 08, 2025 am 09:39 AM
Serialization and deserialization of Python objects are key aspects of any non-trivial program. If you save something to a Python file, you do object serialization and deserialization if you read the configuration file, or if you respond to an HTTP request. In a sense, serialization and deserialization are the most boring things in the world. Who cares about all these formats and protocols? You want to persist or stream some Python objects and retrieve them in full at a later time. This is a great way to see the world on a conceptual level. However, on a practical level, the serialization scheme, format or protocol you choose may determine the speed, security, freedom of maintenance status, and other aspects of the program
Mathematical Modules in Python: Statistics
Mar 09, 2025 am 11:40 AM
Python's statistics module provides powerful data statistical analysis capabilities to help us quickly understand the overall characteristics of data, such as biostatistics and business analysis. Instead of looking at data points one by one, just look at statistics such as mean or variance to discover trends and features in the original data that may be ignored, and compare large datasets more easily and effectively. This tutorial will explain how to calculate the mean and measure the degree of dispersion of the dataset. Unless otherwise stated, all functions in this module support the calculation of the mean() function instead of simply summing the average. Floating point numbers can also be used. import random import statistics from fracti
How to Perform Deep Learning with TensorFlow or PyTorch?
Mar 10, 2025 pm 06:52 PM
This article compares TensorFlow and PyTorch for deep learning. It details the steps involved: data preparation, model building, training, evaluation, and deployment. Key differences between the frameworks, particularly regarding computational grap
Scraping Webpages in Python With Beautiful Soup: Search and DOM Modification
Mar 08, 2025 am 10:36 AM
This tutorial builds upon the previous introduction to Beautiful Soup, focusing on DOM manipulation beyond simple tree navigation. We'll explore efficient search methods and techniques for modifying HTML structure. One common DOM search method is ex
How to Create Command-Line Interfaces (CLIs) with Python?
Mar 10, 2025 pm 06:48 PM
This article guides Python developers on building command-line interfaces (CLIs). It details using libraries like typer, click, and argparse, emphasizing input/output handling, and promoting user-friendly design patterns for improved CLI usability.
What are some popular Python libraries and their uses?
Mar 21, 2025 pm 06:46 PM
The article discusses popular Python libraries like NumPy, Pandas, Matplotlib, Scikit-learn, TensorFlow, Django, Flask, and Requests, detailing their uses in scientific computing, data analysis, visualization, machine learning, web development, and H
