Python實現LRU算法的2種方法

 　　這篇文章主要介紹了Python實現LRU算法的2種方法,本文分別給出了用OrderedDict實現、用dict+list實現兩種方法,需要的朋友可以參考下

　　LRU：least recently used，最近最少使用算法。它的使用場景是：在有限的空間中存儲對象時，當空間滿時，會按一定的原則刪除原有的對象，常用的原則(算法)有LRU，FIFO，LFU等。在計算機的Cache硬件，以及主存到虛擬內存的頁面置換，還有Redis緩存系統中都用到了該算法。我在一次面試和一個筆試時，也遇到過這個問題。

　　LRU的算法是比較簡單的，當對key進行訪問時(一般有查詢，更新，增加，在get()和set()兩個方法中實現即可)時，將該key放到隊列的最前端(或最後端)就行了，這樣就實現了對key按其最後一次訪問的時間降序(或升序)排列，當向空間中增加新對象時，如果空間滿了，刪除隊尾(或隊首)的對象。

　　在Python中，可以使用collections.OrderedDict很方便的實現LRU算法，當然，如果你想不到用OrderedDict，那可以用dict+list來實現。本文主要參考了LRU CACHE IN PYTHON，寫的非常好，既實現了功能，又簡潔易讀。方法一的代碼與參考文章基本相同，方法二是我自己想出來的，比較繁瑣一些，其實OrderedDict本身也是類似的這種機制來實現的有序。

　　不過，下面的實現是有問題的，這個cache的key:value鍵值對中，value只能是不可變類型。因為，如果value是可變類型，那對於同一個key，所有調用get(key)方法返回的value都是指向同一個可變對象的，當修改其中一個value時，那所有的value都會被修改了，即使你沒有調用set()方法也會這樣。這是我們不希望看到的。解決方法我想到了兩種，一是可變對象序列化後再存儲，即將可變對象轉為不可變對象;二是仍存儲可變對象，但get()時，返回一個深拷貝，這樣每個get()調用返回的對象就不會相互影響了。推薦第一種方法。另外，對於key，推薦使用str/unicode類型。

　　當並發時，還會存在一個問題，因為這涉及到對公共資源的寫操作，所以必須要對set()加鎖。其實，在並發情況下，所有對公共資源的寫操作都要加鎖。如果不存在並發的情況，只有單線程，那可以不加鎖。

　　方法一：用OrderedDict實現(推薦)

　　 代碼如下:

　　from collections import OrderedDict

　　class LRUCache(OrderedDict):

　　'''不能存儲可變類型對象，不能並發訪問set()'''

　　def __init__(self,capacity):

　　self.capacity = capacity

　　self.cache = OrderedDict()

　　def get(self,key):

　　if self.cache.has_key(key):

　　value = self.cache.pop(key)

　　self.cache[key] = value

　　else:

　　value = None

　　return value

　　def set(self,key,value):

　　if self.cache.has_key(key):

　　value = self.cache.pop(key)

　　self.cache[key] = value

　　else:

　　if len(self.cache) == self.capacity:

　　self.cache.popitem(last = False) #pop出第一個item

　　self.cache[key] = value

　　else:

　　self.cache[key] = value

　　測試代碼如下

　　 代碼如下:

　　c = LRUCache(5)

　　for i in range(5,10):

　　c.set(i,10*i)

　　print c.cache, c.cache.keys()

　　c.get(5)

　　c.get(7)

　　print c.cache, c.cache.keys()

　　c.set(10,100)

　　print c.cache, c.cache.keys()

　　c.set(9,44)

　　print c.cache, c.cache.keys()

　　輸出如下

　　 代碼如下:

　　OrderedDict([(5, 50), (6, 60), (7, 70), (8, 80), (9, 90)]) [5, 6, 7, 8, 9]

　　OrderedDict([(6, 60), (8, 80), (9, 90), (5, 50), (7, 70)]) [6, 8, 9, 5, 7]

　　OrderedDict([(8, 80), (9, 90), (5, 50), (7, 70), (10, 100)]) [8, 9, 5, 7, 10]

　　OrderedDict([(8, 80), (5, 50), (7, 70), (10, 100), (9, 90)]) [8, 5, 7, 10, 9]

　　方法二：用dict+list實現(不推薦)

　　 代碼如下:

　　class LRUCache(object):

　　'''不能存儲可變類型對象，不能並發訪問set()'''

　　def __init__(self,capacity):

　　self.l = []

　　self.d = {}

　　self.capacity = capacity

　　def get(self,key):

　　if self.d.has_key(key):

　　value = self.d[key]

　　self.l.remove(key)

　　self.l.insert(0,key)

　　else:

　　value = None

　　return value

　　def set(self,key,value):

　　if self.d.has_key(key):

　　self.l.remove(key)

　　elif len(self.d) == self.capacity:

　　oldest_key = self.l.pop()

　　self.d.pop(oldest_key)

　　self.d[key] = value

　　self.l.insert(0, key)

　　測試代碼如下

　　代碼如下:

　　c = LRUCache(5)

　　for i in range(5,10):

　　c.set(i,10*i)

　　print c.d,c.l

　　c.get(5)

　　c.get(7)

　　print c.d,c.l

　　c.set(10,100)

　　print c.d,c.l

　　c.set(9,44)

　　print c.d,c.l

　　輸出為

　　 代碼如下:

　　{8: 80, 9: 90, 5: 50, 6: 60, 7: 70} [9, 8, 7, 6, 5]

　　{8: 80, 9: 90, 5: 50, 6: 60, 7: 70} [7, 5, 9, 8, 6]

　　{5: 50, 7: 70, 8: 80, 9: 90, 10: 100} [10, 7, 5, 9, 8]

　　{5: 50, 7: 70, 8: 80, 9: 44, 10: 100} [9, 10, 7, 5, 8]