Как ограничить размер словаря?

Question

Я хотел бы работать с dict в python, но ограничить количество пар ключ / значение X. Другими словами, если dict в настоящий момент хранит пары X ключ / значение, и я выполняю вставку, я бы как одна из существующих пар, которые будут отброшены. Было бы неплохо, если бы это был наименее недавно вставленный ключ / доступ, но в этом нет необходимости.

Если это есть в стандартной библиотеке, пожалуйста, сэкономьте мне время и укажите на это!

Answer 1

Python 2.7 и 3.1 имеют OrderedDict и существуют реализации на чистом Python для более ранних Python.

from collections import OrderedDict

class LimitedSizeDict(OrderedDict):
    def __init__(self, *args, **kwds):
        self.size_limit = kwds.pop("size_limit", None)
        OrderedDict.__init__(self, *args, **kwds)
        self._check_size_limit()

    def __setitem__(self, key, value):
        OrderedDict.__setitem__(self, key, value)
        self._check_size_limit()

    def _check_size_limit(self):
        if self.size_limit is not None:
            while len(self) > self.size_limit:
                self.popitem(last=False)

Вам также придется переопределить другие методы, которые могут вставлять элементы, такие как update. Основное использование OrderedDict заключается в том, что вы можете легко контролировать то, что выдается, иначе нормальный dict будет работать.

Answer 2

cachetools предоставит вам хорошую реализацию Mapping Hashes, которая делает это (и работает на python 2 и 3).

Выдержка из документации:

Для целей этого модуля кеш является изменяемым отображением фиксированного максимальный размер Когда кеш заполнен, то есть, добавив еще один элемент кэш превысит свой максимальный размер, кеш должен выбрать, какой элемент (ы) сбросить на основе подходящего алгоритма кэширования.

Answer 3

Вот простое решение без LRU Python 2.6+ (в старых Pythons вы могли бы сделать что-то похожее с UserDict.DictMixin, но в 2.6 и выше это не рекомендуется, и ABC из collections предпочтительнее в любом случае ... ):

import collections

class MyDict(collections.MutableMapping):
    def __init__(self, maxlen, *a, **k):
        self.maxlen = maxlen
        self.d = dict(*a, **k)
        while len(self) > maxlen:
            self.popitem()
    def __iter__(self):
        return iter(self.d)
    def __len__(self):
        return len(self.d)
    def __getitem__(self, k):
        return self.d[k]
    def __delitem__(self, k):
        del self.d[k]
    def __setitem__(self, k, v):
        if k not in self and len(self) == self.maxlen:
            self.popitem()
        self.d[k] = v

d = MyDict(5)
for i in range(10):
    d[i] = i
    print(sorted(d))

Как уже упоминалось в других ответах, вы, вероятно, не хотите делать подкласс dict - явное делегирование self.d, к сожалению, бесполезно, но оно гарантирует , что каждый другой метод должным образом предоставлен collections.MutableMapping .

Answer 4

Вот простой и эффективный LRU-кэш, написанный на простом Python-коде, который работает на любом питоне версии 1.5.2 или новее:

class LRU_Cache:

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3         # link fields
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT = 0, 1
        mapping, head, tail = self.mapping, self.head, self.tail

        link = mapping.get(key, head)
        if link is head:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                old_prev, old_next, old_key, old_value = head[NEXT]
                head[NEXT] = old_next
                old_next[PREV] = head
                del mapping[old_key]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(pow, maxsize=3)
    for i in [1,2,3,4,5,3,1,5,1,1]:
        print(i, p(i, 2))

Answer 5

У диктанта нет такого поведения. Вы можете создать свой собственный класс, который делает это, например что-то вроде

class MaxSizeDict(object):
    def __init__(self, max_size):
        self.max_size = max_size
        self.dict = {}
    def __setitem__(self, key, value):
        if key in self.dict:
            self.dict[key] = value    
            return

        if len(self.dict) >= self.max_size:
      ...

Несколько замечаний по этому поводу

• Было бы заманчиво для некоторых подклассов dict здесь. Технически это можно сделать, но это подвержено ошибкам, поскольку методы не зависят друг от друга. Вы можете использовать UserDict.DictMixin, чтобы избавиться от необходимости определять все методы. Есть несколько методов, которые вы могли бы использовать повторно, если у вас есть подкласс dict.
• Диктовщик не знает, что является наименее добавленным ключом, поскольку он неупорядочен.
  • 2.7 будет вводить collections.OrderedDict, но пока хранение ключей в отдельности должно работать нормально (используйте collections.deque в качестве очереди).
  • Если получение самого старого не так уж важно, вы можете просто использовать метод popitem, чтобы удалить один произвольный элемент.
• Я интерпретировал самое старое для обозначения первой вставки, примерно. Вам придется сделать что-то немного другое, чтобы исключить элементы LRU. Наиболее очевидная эффективная стратегия будет заключаться в том, чтобы хранить двусвязный список ключей со ссылками на сами узлы, сохраняемые как значения dict (вместе с реальными значениями). Это становится более сложным, и реализация его на чистом Python несет много накладных расходов.

Answer 6

Было много хороших ответов, но я хочу указать на простую, питонную реализацию кеша LRU. Это похоже на ответ Алекса Мартелли.

from collections import OrderedDict, MutableMapping

class Cache(MutableMapping):
    def __init__(self, maxlen, items=None):
        self._maxlen = maxlen
        self.d = OrderedDict()
        if items:
            for k, v in items:
                self[k] = v

    @property
    def maxlen(self):
        return self._maxlen

    def __getitem__(self, key):
        self.d.move_to_end(key)
        return self.d[key]

    def __setitem__(self, key, value):
        if key in self.d:
            self.d.move_to_end(key)
        elif len(self.d) == self.maxlen:
            self.d.popitem(last=False)
        self.d[key] = value

    def __delitem__(self, key):
        del self.d[key]

    def __iter__(self):
        return self.d.__iter__()

    def __len__(self):
        return len(self.d)

Answer 7

Вы можете создать собственный класс словаря, используя подклассификацию dict. В вашем случае вам придется переопределить __setitem__, чтобы проверить свою собственную длину и удалить что-то, если лимит восстановлен. Следующий пример распечатывает текущую длину после каждой вставки:

class mydict(dict):
    def __setitem__(self, k, v):
        dict.__setitem__(self, k, v)
        print len(self)

d = mydict()
d['foo'] = 'bar'
d['bar'] = 'baz'