Как ограничить размер словаря?
Я хотел бы работать с dict в Python, но ограничить количество пар ключ/значение к X. Другими словами, если бы dict в настоящее время хранит X пар ключ/значение, и я выполняю вставку, я хотел бы, чтобы одна из существующих пар была отброшена. Было бы хорошо, если бы это было, наименьшее количество недавно вставил/получил доступ ключ, но это не абсолютно необходимо.
Если это существует в стандартной библиотеке, сэкономьте мне некоторое время и укажите на это!
4 ответа
Python 2.7 и 3.1 имеют OrderedDict , а также есть реализации на чистом 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 .
Диктат не имеет такого поведения. Вы можете создать свой собственный класс, который будет это делать, например, что-то вроде
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для удаления одного произвольного элемента.
- В версии 2.7 появится
- Я интерпретировал старейший как первый вставленный, приблизительно. Чтобы удалить элементы LRU, нужно сделать что-то немного другое. Наиболее очевидной эффективной стратегией было бы хранение дважды связанного списка ключей со ссылками на сами узлы, хранящиеся как значения dict (наряду с реальными значениями). Это становится все сложнее, и реализация на чистом Python несет большие накладные расходы.
Вы можете создать пользовательский класс словаря, подклассифицировав 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'
Вот простое, без-LRU решение для Python 2.6+ (в старых Python вы могли бы сделать что-то подобное с 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.