Python：构建LRU缓存

Question

我在MongoDB里大约有600,000条记录，格式如下：

feature:category:count

这里面：

• feature可以是任何一个词，
• category是正面或负面，
• count表示某个特征在该类别的文档中出现了多少次。

我想缓存前1000条记录，这样就不用每次都去查询数据库了。

那么，怎么在Python中构建一个LRU缓存呢？或者有没有什么已知的解决方案呢？

Answer 1

Python 3.2 的 functools 模块里有一个叫做 LRU 缓存 的功能。你可以很简单地从 这个地方 把它拿过来，看看是不是需要调整一下才能在 Python 2 上使用（其实不太难，可能只需要用 itertools 替代某些内置函数，如果有问题可以问我）。不过，你需要把查询封装成一个可以调用的东西，并确保它依赖于那些可以被哈希的函数参数。

Answer 2

除了Python 3.2自带的版本外，还有一些LRU缓存的做法可以在Python Cookbook上找到，其中包括这些是由Python核心开发者Raymond Hettinger提供的。

Answer 3

Python 3.3中的 LRU缓存 具有O(1)的插入、删除和查找速度，这意味着这些操作非常快。

它的设计使用了一个循环双向链表来存储数据，链表中的数据是按照从旧到新的顺序排列的，同时还用一个哈希表来快速找到特定的数据。每当我们找到缓存中的数据（称为缓存命中）时，哈希表会帮助我们找到这个数据，并把它移动到链表的最前面。如果找不到数据（称为缓存未命中），就会删除链表中最旧的数据，并在最前面添加新的数据。

下面是一个简化版的LRU缓存实现，只有33行非常基础的Python代码（只使用简单的字典和列表操作）。这个代码可以在Python 2.0及以后的版本上运行（包括PyPy、Jython和Python 3.x）：

class LRU_Cache:

    def __init__(self, original_function, maxsize=1024):
        # Link structure: [PREV, NEXT, KEY, VALUE]
        self.root = [None, None, None, None]
        self.root[0] = self.root[1] = self.root
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

    def __call__(self, *key):
        mapping = self.mapping
        root = self.root
        link = mapping.get(key)
        if link is not None:
            link_prev, link_next, link_key, value = link
            link_prev[1] = link_next
            link_next[0] = link_prev
            last = root[0]
            last[1] = root[0] = link
            link[0] = last
            link[1] = root
            return value
        value = self.original_function(*key)
        if len(mapping) >= self.maxsize:
            oldest = root[1]
            next_oldest = oldest[1]
            root[1] = next_oldest
            next_oldest[0] = root
            del mapping[oldest[2]]
        last = root[0]
        last[1] = root[0] = mapping[key] = [last, root, key, value]
        return value


if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

从Python 3.1开始， OrderedDict 让实现LRU缓存变得更加简单：

from collections import OrderedDict

class LRU_Cache:

    def __init__(self, original_function, maxsize=1024):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = OrderedDict()

    def __call__(self, *key):
        mapping = self.mapping
        try:
            value = mapping[key]
            mapping.move_to_end(key)
        except KeyError:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                mapping.popitem(False)
            mapping[key] = value
        return value