快捷導(dǎo)航

Python實(shí)現(xiàn)LRU算法的2種方法

更新時(shí)間：2015年06月24日 09:28:35 投稿：junjie

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

LRU：least recently used，最近最少使用算法。它的使用場(chǎng)景是：在有限的空間中存儲(chǔ)對(duì)象時(shí)，當(dāng)空間滿時(shí)，會(huì)按一定的原則刪除原有的對(duì)象，常用的原則（算法）有LRU，F(xiàn)IFO，LFU等。在計(jì)算機(jī)的Cache硬件，以及主存到虛擬內(nèi)存的頁(yè)面置換，還有Redis緩存系統(tǒng)中都用到了該算法。我在一次面試和一個(gè)筆試時(shí)，也遇到過(guò)這個(gè)問(wèn)題。

LRU的算法是比較簡(jiǎn)單的，當(dāng)對(duì)key進(jìn)行訪問(wèn)時(shí)（一般有查詢，更新，增加，在get()和set()兩個(gè)方法中實(shí)現(xiàn)即可）時(shí)，將該key放到隊(duì)列的最前端（或最后端）就行了，這樣就實(shí)現(xiàn)了對(duì)key按其最后一次訪問(wèn)的時(shí)間降序（或升序）排列，當(dāng)向空間中增加新對(duì)象時(shí)，如果空間滿了，刪除隊(duì)尾（或隊(duì)首）的對(duì)象。

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

不過(guò)，下面的實(shí)現(xiàn)是有問(wèn)題的，這個(gè)cache的key:value鍵值對(duì)中，value只能是不可變類型。因?yàn)?，如果value是可變類型，那對(duì)于同一個(gè)key，所有調(diào)用get(key)方法返回的value都是指向同一個(gè)可變對(duì)象的，當(dāng)修改其中一個(gè)value時(shí)，那所有的value都會(huì)被修改了，即使你沒(méi)有調(diào)用set()方法也會(huì)這樣。這是我們不希望看到的。解決方法我想到了兩種，一是可變對(duì)象序列化后再存儲(chǔ)，即將可變對(duì)象轉(zhuǎn)為不可變對(duì)象；二是仍存儲(chǔ)可變對(duì)象，但get()時(shí)，返回一個(gè)深拷貝，這樣每個(gè)get()調(diào)用返回的對(duì)象就不會(huì)相互影響了。推薦第一種方法。另外，對(duì)于key，推薦使用str/unicode類型。

當(dāng)并發(fā)時(shí)，還會(huì)存在一個(gè)問(wèn)題，因?yàn)檫@涉及到對(duì)公共資源的寫操作，所以必須要對(duì)set()加鎖。其實(shí)，在并發(fā)情況下，所有對(duì)公共資源的寫操作都要加鎖。如果不存在并發(fā)的情況，只有單線程，那可以不加鎖。

方法一：用OrderedDict實(shí)現(xiàn)（推薦）

復(fù)制代碼代碼如下:

from collections import OrderedDict

class LRUCache(OrderedDict):
'''不能存儲(chǔ)可變類型對(duì)象，不能并發(fā)訪問(wèn)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出第一個(gè)item
                self.cache[key] = value
            else:
                self.cache[key] = value

測(cè)試代碼如下

復(fù)制代碼代碼如下:

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()

輸出如下

復(fù)制代碼代碼如下:

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實(shí)現(xiàn)（不推薦）

復(fù)制代碼代碼如下:

class LRUCache(object):
    '''不能存儲(chǔ)可變類型對(duì)象，不能并發(fā)訪問(wèn)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è)試代碼如下

復(fù)制代碼代碼如下:

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

輸出為

復(fù)制代碼代碼如下:

{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]

您可能感興趣的文章: