Python实现LRU Cache

LRU: 最近最少使用算法。

使用场景：在有限的空间存储对象时，当空间满时，按照一定的原则删除原有对象。 常用的算法有LRU，FIFO，LFU。如memcached缓存系统即使用的LRU。

LRU的算法是比较简单的，当对key进行访问时时，将该key放到队列的最前端（或最后端）就行了，这样就实现了对key按其最后一次访问的时间降序（或升序）排列。 当向空间中增加新对象时，如果空间满了，删除队尾（或队首）的对象。

在Python中，可以使用collections.OrderedDict很方便的实现LRU算法。

# coding: utf-8
import collections


class LRUCache(collections.OrderedDict):
    def __init__(self, size=5):
        self.size = size
        self.cache = collections.OrderedDict()

    def get(self, key):
        if self.cache.has_key(key):
            val = self.cache.pop(key)
            self.cache[key] = val
        else:
            val = None

        return val

    def set(self, key, val):
        if self.cache.has_key(key):
            val = self.cache.pop(key)
            self.cache[key] = val
        else:
            if len(self.cache) == self.size:
                self.cache.popitem(last=False)
                self.cache[key] = val
            else:
                self.cache[key] = val


if __name__ == '__main__':
    """ test """
    cache = LRUCache(6)

    for i in range(10):
        cache.set(i, i)

    for i in range(10):
        import random

        i = random.randint(1, 20)
        print 'cache', cache.cache.keys()
        if cache.get(i):
            print 'hit, %s\n' % i
        else:
            print 'not hit, %s\n' % i

这个实现存在的问题：

1. cache的value是能是不可变对象。
2. 在并发时，多个线程对缓存进行读写，那么必须对set()操作加锁。TODO 实现一个支持并发访问的LRU cache
3. value不能设置过期时间，而常用的redis和memcached都支持给value设置expire time。TODO 实现一个支持expire的LRU cache

---