Python实现的一个简单LRU cache
起因：我的同事需要一个固定大小的cache，如果记录在cache中，直接从cache中读取，否则从数据库中读取。python的dict是一个非常简单的cache,但是由于数据量很大，内存很可能增长的过大，因此需要限定记录数，并用LRU算法丢弃旧记录。key是整型，value是10KB左右的python对象
分析：
1）可以想到，在对于cache，我们需要维护key->value的关系
2）而为了实现LRU，我们又需要一个基于时间的优先级队列，来维护 timestamp ->(key,value)的关系
3）当cache中的记录数达到一个上界maxsize时，需要将timestamp最小的(key,value)出队列
4)当一个（key,value)被命中时，实际上我们需要将它从队列中，移除并插入到队列的尾部。
从分析可以看出我们的cache要达到性能最优需要满足上面的四项功能，对于队表的快速移除和插入，链表显然是最优的选择，为了快速移除，最好使用双向链表，为了插入尾部，需要有指向尾部的指针。
下面用python来实现：
#encoding=utf-8
classLRUCache(object): def__init__(self,maxsize): #cache的最大记录数 self.maxsize=maxsize #用于真实的存储数据 self.inner_dd={} #链表-头指针 self.head=None #链表-尾指针 self.tail=None
defset(self,key,value): #达到指定大小 iflen(self.inner_dd)>=self.maxsize: self.remove_head_node()
node=Node() node.data=(key,value) self.insert_to_tail(node) self.inner_dd[key]=node
definsert_to_tail(self,node): ifself.tailisNone: self.tail=node self.head=node else: self.tail.next=node node.pre=self.tail self.tail=node
defremove_head_node(self): node=self.head delself.inner_dd[node.data[0]] node=None self.head=self.head.next self.head.pre=None defget(self,key): ifkeyinself.inner_dd: #如果命中,需要将对应的节点移动到队列的尾部 node=self.inner_dd.get(key) self.move_to_tail(node) returnnode.data[1] returnNone
defmove_to_tail(self,node): #只需处理在队列头部和中间的情况 ifnot(node==self.tail): ifnode==self.head: self.head=node.next self.head.pre=None self.tail.next=node node.pre=self.tail node.next=None self.tail=node else: pre_node=node.pre next_node=node.next pre_node.next=next_node next_node.pre=pre_node
self.tail.next=node node.pre=self.tail node.next=None self.tail=node
classNode(object): def__init__(self): self.pre=None self.next=None #(key,value) self.data=None
def__eq__(self,other): ifself.data[0]==other.data[0]: returnTrue returnFalse def__str__(self): returnstr(self.data)
if__name__=='__main__': cache=LRUCache(10) foriinxrange(1000): cache.set(i,i+1) cache.get(2) forkeyincache.inner_dd: printkey,cache.inner_dd[key]