Реализация кеша с ограничением по числу элементов на Python — решения: простое и посложнее

[@seriyPS]

docs.python.org/library/collections.html#collections.deque =)

[@Oronro]

и результаты тестов (Linux x64 Python 2.7.3):

Simple: min 1.85775, max 1.91843, avg 1.87948
Fast: min 0.10335, max 0.10573, avg 0.10444
Deque: min 0.00592, max 0.00609, avg 0.00598

[@JustAMan]

Про collections я в курсе (особенно хорош там defaultdict).

deque организует немного не ту модель — там быстрые добавление/удаление в любой из концов очереди.
В описанном тут случае нужен быстрый случайный доступ (вместе с удалением из произвольного места, в т.ч. из середины, что в deque делается за O(N), а в приведённой реализации — за константное время).

Правда, приведённые в статье измерения этого действительно не отражают :)

Если я заблуждаюсь — буду рад увидеть хотя бы кусочек реализации, типа метода touchCache из первого класса.

[@seriyPS]

хм, пожалуй тогда подойдет OrderedDict… попозже проверю

[@JustAMan]

Сначала ответил немного мимо… В-общем, выходит, что OrderedDict здесь — почти идеал! :) Не сильно уступает в скорости работы сложному решению, легко читается и ест на порядок меньше памяти.

Спасибо! :)

[@JustAMan]

Похоже, collections.OrderedDict — это нечто среднее. По результатам моих проверок, работает почти так же быстро, как сложное решение, при этом выглядит гораздо читабельнее.

Пожалуй, добавлю в статью.

[@tbd]

вдогонку такая реализация кеша

class ListDictBasedCache(object):
    __slots__ = ['__key2value', '__maxCount', '__weights']
    def __init__(self, maxCount):
        self.__maxCount = maxCount
        self.__key2value = {}# key->value
        self.__weights = []# keys ordered in LRU

    def __updateWeight(self, key):
        try:
            self.__weights.remove(key)
        except ValueError:
            pass
        self.__weights.append(key)# add key to end
        if len(self.__weights) > self.__maxCount:
            _key = self.__weights.pop(0)# remove first key
            self.__key2value.pop(_key)

    def __getitem__(self, key):
        try:
            value = self.__key2value[key]
            self.__updateWeight(key)
            return value
        except KeyError:
            raise KeyError("key %s not found" % key)

    def __setitem__(self, key, value):
        self.__key2value[key] = value
        self.__updateWeight(key)

    def __str__(self):
        return str(self.__key2value)

замеры на вашем тесте
DictBasedCache: min 0.00702, max 0.00785, avg 0.00721
FastCache: min 0.13259, max 0.13793, avg 0.13528
ListDictBasedCache: min 0.07482, max 0.07965, avg 0.07638
ODCache: min 0.16472, max 0.16917, avg 0.16693

здесь для сравнения добавлен DictBasedCache для сравнения с обычным словарём

class DictBasedCache(dict):
    def __init__(self, cacheSize):
        self.cacheSize = cacheSize
        dict.__init__(self)

[@JustAMan]

Случайно ответил ниже

[@JustAMan]

Во-первых, хранение ключ-значение в стандартном dict перерасходует память — этот список будет держать ссылки на объект, даже когда снаружи refcount станет равным нулю, и, пока кэш не переполнится, устаревшие (с точки зрения кода-пользователя кэша) данные не удалятся. В этом плане WeakValueDictionary лучше.

А во-вторых — странные немного результаты. Как я выяснил — приведённая в статье реализация ODCache — нерабочая, и при рабочей реализации память оно ест на уровне остальных, а работает чуть медленнее FastCache. Измерения в статье не проверяют чтение из кэша совершенно.
Кстати, надо обновить статью, привести там рабочий ODCache…

Ваш вариант — это практически SimpleCache, приведённый в самом начале, разве что удаление элемента устроено лучше. Но дело в том, что операции pop() и remove() в принципе довольно дорогие — в случае с первой надо большой объём данных переместить, со второй — пробежаться (в худшем случае) до края массива, а это за линейное время.

В общем мне кажется, что где-то в измерения закралась ошибка. Может быть, мал объём данных для тестов, или ещё чего… Надо будет подумать :)

[@JustAMan]

Померил, пока это решение в лидерах… хотя я всё равно не понимаю, почему :) Возможно, потому, что list() реализован в нативном коде, а FastCache — чисто питоновский.

[@tbd]

вообще решение я писал в лоб
старался только минимум логики реализовывать на python'е и максимально использовать builtin объекты
по сути оно так и вышло, на питоне только доступ к атрибутам и вызов методов

что касается лишней памяти: я так думаю если вместо ключа хранить хэш инстанса ключа hash(key), то потери будут сильно меньше