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

Question

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

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

Answer 1

Python 2.7 и 3.1 имеют Упорядоченный запрет и есть реализации на чистом Python для более ранних Pythons.

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 ( кэш - инструменты ) предоставит вам хорошую реализацию отображения хэшей, которая делает это (и это работает на python 2 и 3).

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

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

Answer 3

Вот простое решение без использования LRU на Python 2.6+ (в старых Pythons вы могли бы сделать что-то подобное с UserDict.DictMixin, но в версии 2.6 и выше это не рекомендуется, а азбука из 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, который работает на любом 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

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

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.
• Dict не знает, какой ключ был добавлен последним, поскольку dicts неупорядочены.
  • 2.7 представит collections.OrderedDict, но на данный момент приведение ключей в порядок по отдельности должно работать нормально (используйте collections.deque в виде очереди).
  • Если получение самого старого не так уж важно, вы можете просто использовать popitem способ удаления одного произвольного элемента.
• Я интерпретирую слово "самый старый" примерно как "первая вставка".Вам пришлось бы сделать что-то немного другое, чтобы исключить элементы LRU.Наиболее очевидной эффективной стратегией было бы сохранение двусвязного списка ключей со ссылками на сами узлы, хранящиеся в виде значений dict (наряду с реальными значениями).Это становится все сложнее, и реализация его на чистом Python сопряжена с большими накладными расходами.

Answer 6

Вы можете создать пользовательский класс словаря, создав подкласс 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'

Answer 7

Было много хороших ответов, но я хочу указать на простую реализацию pythonic для кэша 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)