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

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

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

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

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

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)

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

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

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

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