緩存是指可以進行高速數(shù)據(jù)交換的存儲器，它先于內(nèi)存與CPU交換數(shù)據(jù)，因此速度很快。緩存就是把一些數(shù)據(jù)暫時存放于某些地方，可能是內(nèi)存，也有可能硬盤。下面給大家介紹Python實現(xià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ù)用二進制展開，得到的二進制數(shù)據(jù)映射到緩存字段上，要檢驗是否已經(jīng)緩存過，僅需要去查找對應的映射位置即可，如果全部匹配上，則已經(jīng)緩存。

# 二進制就是個二叉樹
# 如下面可以表示出來的數(shù)據(jù)有0, 1, 2, 3四個(兩個樹獨立)

0 1
/ \ / \
0 1 0 1

因此對緩存的操作就轉(zhuǎn)化為對二叉樹的操作，添加和查找只要在二叉樹上找到對應路徑的node即可。

算法關鍵代碼：

def _read_bit(self, data, position):
return (data >> position) & 0x1
def _write_bit(self, data, position, value):
return data | value << position

實際使用效果如何呢?

在和Python默認的 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)存雖然也不是很大，當相較于 ByteCache 來說，則大上很多。

但 ByteCache 的方式來緩存，最大的問題是當碰到非常大的隨機數(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. 此方法的目標是用時間換取空間，切勿在時間緊迫度高的地方使用

2. 非常適用于大量定長，且數(shù)據(jù)本身比較小的情況下使用

3. 接2，非常不建議在大量不定長的數(shù)據(jù)，而且數(shù)據(jù)本身比較大的情況下使用

以上內(nèi)容是小編給大家介紹的Python實現(xiàn)以時間換空間的緩存替換算法，希望對大家有所幫助！

您可能感興趣的文章: