Python实现LRU算法的2种方法

发布时间：2020-12-16 22:38:32 所属栏目：Python 来源：网络整理

导读：LRU：least recently used，最近最少使用算法。它的使用场景是：在有限的空间中存储对象时，当空间满时，会按一定的原则删除原有的对象，常用的原则（算法）有LRU，FIFO，LFU等。在计算机的Cache硬件，以及主存到虚拟内存的页面置换，还有Redis缓存系统中都

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,90),(5,70)])     [6,9,5,7]

OrderedDict([(8,(10,100)])   [8,10]

OrderedDict([(8,100),90)])   [8,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,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*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,5]

{8: 80,7: 70}   [7,6]

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!