Python實現(xiàn)以時間換空間的緩存替換算法
緩存是指可以進(jìn)行高速數(shù)據(jù)交換的存儲器，它先于內(nèi)存與CPU交換數(shù)據(jù)，因此速度很快。緩存就是把一些數(shù)據(jù)暫時存放于某些地方，可能是內(nèi)存，也有可能硬盤。
在使用Scrapy爬網(wǎng)站的時候，產(chǎn)生出來的附加產(chǎn)物，因為在Scrapy爬取的時候，CPU的運行時間緊迫度不高（訪問頻次太高容易被封禁），借此機會難得來上一下，讓自己的內(nèi)存解放一下。
算法原理：
通過將要緩存的數(shù)據(jù)用二進(jìn)制展開，得到的二進(jìn)制數(shù)據(jù)映射到緩存字段上，要檢驗是否已經(jīng)緩存過，僅需要去查找對應(yīng)的映射位置即可，如果全部匹配上，則已經(jīng)緩存。
# 二進(jìn)制就是個二叉樹
# 如下面可以表示出來的數(shù)據(jù)有0, 1, 2, 3四個(兩個樹獨立)
0 1
/ \ / \
0 1 0 1
因此對緩存的操作就轉(zhuǎn)化為對二叉樹的操作，添加和查找只要在二叉樹上找到對應(yīng)路徑的node即可。
算法關(guān)鍵代碼：
def _read_bit(self, data, position): return (data >> position) & 0x1 def _write_bit(self, data, position, value): return data | value << position
實際使用效果如何呢?
在和Python默認(rèn)的 set 相比較，得出測試結(jié)果如下（存取整型，不定長字符串，定長字符串）：
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...
測試下來，內(nèi)存消耗控制的比較好，一直在56字節(jié)，而是用 set 的內(nèi)存雖然也不是很大，當(dāng)相較于 ByteCache 來說，則大上很多。
但 ByteCache 的方式來緩存，最大的問題是當(dāng)碰到非常大的隨機數(shù)據(jù)時，消耗時間會比較驚人。如下面這種隨機長度的字符串緩存測試結(jié)果：
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個數(shù)據(jù)中，添加消耗31s，查找消耗44s，而 set 接近于0，單條數(shù)據(jù)也需要16ms（均值）才能完成讀/寫操作。
不過，正如開頭說的，在緊迫度不是很高的Scrapy中，這個時間并不會太過于窘迫，更何況在Scrapy中，一般是用來緩存哈希后的數(shù)據(jù)，這些數(shù)據(jù)的一個重要特性是定長，定長在本緩存算法中還是表現(xiàn)不錯的，在64位長度的時候，均值才0.5ms。而與此同時倒是能在大量緩存的時候，釋放出比較客觀的內(nèi)存。
如果有更好的緩存算法能讓速度在上新臺階，也是無比期待的。。。
總結(jié)：
1. 此方法的目標(biāo)是用時間換取空間，切勿在時間緊迫度高的地方使用
2. 非常適用于大量定長，且數(shù)據(jù)本身比較小的情況下使用
3. 接2，非常不建議在大量不定長的數(shù)據(jù)，而且數(shù)據(jù)本身比較大的情況下使用
以上內(nèi)容是小編給大家介紹的Python實現(xiàn)以時間換空間的緩存替換算法，希望對大家有所幫助！
相關(guān)文章
在Python的Django框架中調(diào)用方法和處理無效變量
這篇文章主要介紹了在Python的Django框架中調(diào)用方法和處理無效變量的方法,是Django編程中的基礎(chǔ)操作,需要的朋友可以參考下2015-07-07
在ubuntu16.04中將python3設(shè)置為默認(rèn)的命令寫法
這篇文章主要介紹了在ubuntu16.04中將python3設(shè)置為默認(rèn)python的方法，非常不錯，具有一定的參考借鑒價值，需要的朋友參考下吧2018-10-10
這篇文章主要為大家介紹了AI與Python啟發(fā)式搜索概念詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
python實現(xiàn)ftp文件傳輸系統(tǒng)(案例分析)
最近做了一個簡單的文件傳輸系統(tǒng)，基于ftp協(xié)議，使用python語言開發(fā)，雖然python里面已經(jīng)有ftplib模塊，可以很容易的實現(xiàn)ftp服務(wù)器，這篇文章主要介紹了python實現(xiàn)ftp文件傳輸系統(tǒng)的案例分析,需要的朋友可以參考下2020-03-03
Django 解決上傳文件時,request.FILES為空的問題
這篇文章主要介紹了Django 解決上傳文件時,request.FILES為空的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-05-05
Python?httpstat是一個強大的命令行工具，用于深入了解HTTP請求的性能和狀態(tài)信息，本文將介紹Python?httpstat的基本用法、功能特性、示例代碼以及實際應(yīng)用場景，幫助大家更好地理解和利用這個有用的工具2024-01-01
Python pygame實現(xiàn)中國象棋單機版源碼
今天給大家?guī)淼氖顷P(guān)于Python實戰(zhàn)的相關(guān)知識,文章圍繞著用Python pygame實現(xiàn)中國象棋單機版展開,文中有非常詳細(xì)的代碼示例,需要的朋友可以參考下2021-06-06
Selenium是一個用于自動化瀏覽器操作的Python庫,常用于Web應(yīng)用的測試和爬蟲等場景,本文給大家介紹Python中Selenium的基本使用教程,感興趣的朋友一起看看吧2023-11-11
基于python+selenium自動健康打卡的實現(xiàn)代碼
這篇文章主要介紹了基于python+selenium自動健康打卡,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
這篇文章主要為大家介紹了Python中如何自定義異常，以及自定義拋出異常的關(guān)鍵字—raise的用法，文中示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-03-03