Python: создание кэша LRU

Question

у меня около 6,00,000 entries in MongoDB в следующем формате:

feature:category:count

где

• функция может быть любым словом,
• категория положительная или отрицательная, а
• count сообщает, сколько раз в документе появлялась функция для этой категории.

Я хочу кэшировать 1000 лучших кортежей, скажем, чтобы не каждый раз запрашивать базу данных.

Как построить кэш LRU в Python? Или есть какие-то известные решения для этого?

Answer 1

Кэш LRU в Python3.3 имеет O (1) вставку, удаление и поиск.

В дизайне используется круговой двусвязный список записей (упорядоченный от самого старого к новейшему) и хеш-таблица для поиска отдельных ссылок.Хиты кеша используют хеш-таблицу, чтобы найти соответствующую ссылку и переместить ее в начало списка.Cache пропускает удаление самой старой ссылки и создает новую ссылку в начале связанного списка.

Вот упрощенная (но быстрая) версия в 33 строках очень простого Python (с использованием только простых операций словаря и списка).Он работает на Python2.0 и более поздних версиях (или PyPy, Jython или 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))

Answer 2

Помимо версии, включенной в Python 3.2, в Python Cookbook есть рецепты кэша LRU, включая эти от разработчика ядра Python Раймонда Хеттингера.

Answer 3

Python 3.2 functools включает LRU-кеш . Вы можете легко выбрать его из repo , проверить, нужно ли настроить его для работы с Python 2 (не должно быть слишком сложно - возможно, с использованием itertools вместо некоторых встроенных функций - спросите, нужна ли вам помощь) и будет сделано. Вам нужно заключить запрос в вызываемый объект и убедиться, что он зависит от аргументов (хэшируемых) функций.

Answer 4

Существуют также обратные порты версии lru_cache для Python 3.3, такой как this , которая работает на Python 2.7. Если вас интересуют два уровня кэширования (если он не кэшируется в экземпляре, он будет проверять общий кеш), то я создал lru2cache на основе обратного порта lru_cache.