Python:建立LRU快取 [英] Python: building an LRU cache

问题描述

我有6,00,000 entries in MongoDB左右，格式如下:

feature:category:count

其中

• 功能可以是任何单词，
• 类别是肯定的还是否定的，并且
• 计数告诉您该类别的功能在文档中出现了多少次.

• feature could be any word,
• category is positive or negative, and
• count tells how many times a feature occurred in a document for that category.

我想缓存前1000个元组，这样可以避免每次都不查询数据库.

I want to cache the top 1000 tuples, let's say so as not to query database each time.

如何在Python中构建LRU缓存?还是对此有任何已知的解决方案?

How does one build an LRU cache in Python? Or are there any known solutions to this?

推荐答案

LRU缓存具有O(1)插入，删除和搜索功能.

The LRU cache in Python3.3 has O(1) insertion, deletion, and search.

设计使用圆形双向链接的条目列表(从最旧到最新排列)和哈希表来查找各个链接.缓存命中使用哈希表查找相关链接，并将其移到列表的开头.缓存未命中会删除最旧的链接，并在链接列表的开头创建一个新链接.

The design uses a circular doubly-linked list of entries (arranged oldest-to-newest) and a hash table to locate individual links. Cache hits use the hash table to find the relevant link and move it to the head of the list. Cache misses delete the oldest link and create a new link at the head of the linked list.

这是33行非常基本的Python(仅使用简单的字典和列表操作)的简化(但快速)版本.它可以在Python2.0和更高版本(或PyPy或Jython或Python3.x)上运行:

Here's a simplified (but fast) version in 33 lines of very basic Python (using only simple dictionary and list operations). It runs on Python2.0 and later (or PyPy or Jython or Python3.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:建立LRU快取的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！