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
本文由 络壳 原创或整理,转载请注明出处