python教程-如何通过Python来完成一个简单的LRU算法

作者:在线学习平台更新于： 2015-06-25 16:44:49

今天给大家带来一个python教程，教你如何通过Python来完成一个简单的LRU算法，本文例举的方法有两种：分别是用OrderedDict实现、另一个是用dict+list来实现，具体的操作方法可以参考一下，更多的方式大家也可以集思广益，这样才能学到更多的编程语言知识。

　　LRU：least recently used，最近最少使用算法。它的使用场景是：在有限的空间中存储对象时，当空间满时，会按一定的原则删除原有的对象，常用的原则(算法)有LRU，FIFO，LFU等。在计算机的Cache硬件，以及主存到虚拟内存的页面置换，还有Redis缓存系统中都用到了该算法。我在一次面试和一个笔试时，也遇到过这个问题。
      LRU：现在相对比较少使用算法，least recently used。其使用方案是：在有限的空间时，以存储对象，当充满时，将根据原始对象的某些原则除去，常用的原则(算法)有LRU，FIFO，LFU等。缓存在计算机硬件，以及主存储器的虚拟存储器页的更换，还有Redis的缓存系统中使用到该算法。
      LRU算法相对简单，当访问密钥（一般查询，更新，添加，就可以实现get（）和（）设置两个方法）时，就行了钥匙插入队列的前面（或最后端），这样当添加新对象的空间，如果空间是充分实现其关键上次访问时间降序（或上升）命令，删除尾部（或一队）的对象。
　　我们在使用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()加锁。其实，在并发情况下，所有对公共资源的写操作都要加锁。如果不存在并发的情况，只有单线程，那可以不加锁。
具体的python教程操作如下：
　　方法一：用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]
最后，本次的python教程就结束了，更多关于如何利用python来实现实现LRU算法的方法，以上的两种方法可以供大家参考学习，至于其他的方法的话，大家可以再做交流，只要不断的推陈出新，集思广益，才能创造出更多便捷的操作方式。如需学习python基础教程可关注课课家网络学习平台，推荐给初学者的Python视频教程。