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