緩存是指可以進行高速數(shù)據(jù)交換的存儲器，它先于內存與CPU交換數(shù)據(jù)，因此速度很快。緩存就是把一些數(shù)據(jù)暫時存放于某些地方，可能是內存，也有可能硬盤。
在使用Scrapy爬網(wǎng)站的時候，產(chǎn)生出來的附加產(chǎn)物，因為在Scrapy爬取的時候，CPU的運行時間緊迫度不高（訪問頻次太高容易被封禁），借此機會難得來上一下，讓自己的內存解放一下。
算法原理：
通過將要緩存的數(shù)據(jù)用二進制展開，得到的二進制數(shù)據(jù)映射到緩存字段上，要檢驗是否已經(jīng)緩存過，僅需要去查找對應的映射位置即可，如果全部匹配上，則已經(jīng)緩存。
# 二進制就是個二叉樹
# 如下面可以表示出來的數(shù)據(jù)有0, 1, 2, 3四個(兩個樹獨立)
0 1
/ / / /
0 1 0 1
因此對緩存的操作就轉化為對二叉樹的操作，添加和查找只要在二叉樹上找到對應路徑的node即可。
算法關鍵代碼：
def _read_bit(self, data, position):return (data >> position) & 0x1def _write_bit(self, data, position, value):return data | value << position
實際使用效果如何呢?
在和Python默認的 set 相比較，得出測試結果如下（存取整型，不定長字符串，定長字符串）：
Please select test mode:4Please enter test times:1000====================================================================================================TEST RESULT::====================================================================================================set() bytecacheitems 1000 1000add(s) 0.0 0.0209999084473read(s) 0.0 0.0149998664856hits 1000 1000missed 0 0size 32992 56add(s/item) 0.0 2.09999084473e-05read(s/item) 0.0 2.09999084473e-05====================================================================================================size (set / bytecache): 589.142857143add time (bytecache / set): N/Aread time (bytecache / set): N/A====================================================================================================...test fixed length & int data end...====================================================================================================TEST RESULT::====================================================================================================set() bytecacheitems 1000 1000add(s) 0.00100016593933 6.1740000248read(s) 0.0 7.21300005913hits 999 999missed 0 0size 32992 56add(s/item) 1.00016593933e-06 0.0061740000248read(s/item) 0.0 0.0061740000248====================================================================================================size (set / bytecache): 589.142857143add time (bytecache / set): 6172.97568534read time (bytecache / set): N/A====================================================================================================...test mutative length & string data end...====================================================================================================TEST RESULT::====================================================================================================set() bytecacheitems 1000 1000add(s) 0.0 0.513999938965read(s) 0.0 0.421000003815hits 999 999missed 0 0size 32992 56add(s/item) 0.0 0.000513999938965read(s/item) 0.0 0.000513999938965====================================================================================================size (set / bytecache): 589.142857143add time (bytecache / set): N/Aread time (bytecache / set): N/A====================================================================================================...test Fixed length(64) & string data end...
測試下來，內存消耗控制的比較好，一直在56字節(jié)，而是用 set 的內存雖然也不是很大，當相較于 ByteCache 來說，則大上很多。
但 ByteCache 的方式來緩存，最大的問題是當碰到非常大的隨機數(shù)據(jù)時，消耗時間會比較驚人。如下面這種隨機長度的字符串緩存測試結果：
Please select test mode:2Please enter test times:2000====================================================================================================TEST RESULT::====================================================================================================set() bytecacheitems 2000 2000add(s) 0.00400018692017 31.3759999275read(s) 0.0 44.251999855hits 1999 1999missed 0 0size 131296 56add(s/item) 2.00009346008e-06 0.0156879999638read(s/item) 0.0 0.0156879999638====================================================================================================size (set / bytecache): 2344.57142857add time (bytecache / set): 7843.63344856read 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。而與此同時倒是能在大量緩存的時候，釋放出比較客觀的內存。
如果有更好的緩存算法能讓速度在上新臺階，也是無比期待的。。。
總結：
1. 此方法的目標是用時間換取空間，切勿在時間緊迫度高的地方使用
2. 非常適用于大量定長，且數(shù)據(jù)本身比較小的情況下使用
3. 接2，非常不建議在大量不定長的數(shù)據(jù)，而且數(shù)據(jù)本身比較大的情況下使用
以上內容是小編給大家介紹的Python實現(xiàn)以時間換空間的緩存替換算法，希望對大家有所幫助！
新聞熱點
疑難解答
圖片精選
