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

class LRUCache(object):

 def __init__(self, maxsize):

 # cache 的最大记录数

 self.maxsize = maxsize

 # 用于真实的存储数据

 self.inner_dd = {}

 # 链表-头指针

 self.head = None

 # 链表-尾指针 

 self.tail = None
 def set(self, key, value):

 # 达到指定大小 

 if len(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
 def insert_to_tail(self, node):

 if self.tail is None:

 self.tail = node

 self.head = node

 else:

 self.tail.next = node

 node.pre = self.tail

 self.tail = node
 def remove_head_node(self):

 node = self.head

 del self.inner_dd[node.data[0]]

 node = None

 self.head = self.head.next

 self.head.pre = None

 def get(self, key):

 if key in self.inner_dd:

 # 如果命中, 需要将对应的节点移动到队列的尾部

 node = self.inner_dd.get(key)

 self.move_to_tail(node)

 return node.data[1]

 return None
 def move_to_tail(self, node):

 # 只需处理在队列头部和中间的情况

 if not (node == self.tail):

 if node == 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
class Node(object):

 def __init__(self):

 self.pre = None

 self.next = None

 # (key, value)

 self.data = None
 def __eq__(self, other):

 if self.data[0] == other.data[0]:

 return True

 return False

 def __str__(self):

 return str(self.data)
if __name__ == '__main__':

 cache = LRUCache(10)

 for i in xrange(1000):

 cache.set(i, i+1)

 cache.get(2)

 for key in cache.inner_dd:

 print key, cache.inner_dd[key]

本文Python实现的一个简单LRU cache到此结束。不论何时，只要你心怀自大、自满、自私自利的想法去做任何事情的话，你都不会成功。不论何时，你只要变得无私，充满爱心，也不自大自满时，你会发现在自己的背后，有一股强大的力量，使你在人生正确的方向迈进时，永远不会失败。小编再次感谢大家对我们的支持！