¿Cómo limitar el tamaño de un diccionario?

Me gustaría trabajar con un dict en python, pero limitar el número de pares de clave / valor a X. En otras palabras, si el dict está almacenando actualmente los pares de clave / valor de X y realizo una inserción, me gustaría uno de Los pares existentes para ser descartados. Sería bueno si se tratara de la clave de acceso / inserción menos reciente, pero eso no es completamente necesario.

Si esto existe en la biblioteca estándar, por favor, ahórrame un tiempo y señálalo.

Python 2.7 y 3.1 tienen OrderedDict y existen implementaciones de Python puro para Pythons anteriores.

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) 

También tendría que anular otros métodos que pueden insertar elementos, como la update . El uso principal de OrderedDict es para que pueda controlar lo que se hace estallar fácilmente, de lo contrario un dict normal funcionaría.

cachetools le proporcionará una buena implementación de Mapping Hashes que hace esto (y funciona en python 2 y 3).

Extracto de la documentación:

Para los fines de este módulo, un caché es una asignación mutable de un tamaño máximo fijo. Cuando el caché está lleno, es decir, al agregar otro elemento, el caché excedería su tamaño máximo, el caché debe elegir qué elemento (s) descartar en función de un algoritmo de caché adecuado.

Aquí hay una solución Python 2.6+ simple, sin LRU (en Pythons más antiguos, podría hacer algo similar con UserDict.DictMixin , pero en 2.6 y mejor no se recomienda, y el ABC de las collections es preferible de todos modos …):

 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)) 

Como se mencionó en otras respuestas, es probable que no desee self.d subclase dict: la delegación explícita a self.d es lamentablemente muy sencilla, pero garantiza que las collections.MutableMapping proporcionen todos los otros métodos de manera adecuada.

Aquí hay una memoria caché LRU simple y eficiente escrita con el sencillo código Python que se ejecuta en cualquier versión de Python 1.5.2 o posterior:

 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)) 

Un dict no tiene este comportamiento. Podrías hacer tu propia clase que haga esto, por ejemplo algo como

 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: ... 

Algunas notas sobre esto

  • Sería tentador para algunos dictar la dict aquí. Técnicamente puede hacer esto, pero es propenso a errores porque los métodos no dependen unos de otros. Puede usar UserDict.DictMixin para evitar tener que definir todos los métodos. Hay pocos métodos que podría reutilizar si hace una subclase de dict .
  • Un dict no sabe cuál es la clave que se agregó recientemente, ya que los dictados no están ordenados.
    • 2.7 introducirá collections.OrderedDict , pero por ahora, mantener las claves en orden por separado debería funcionar bien (utilice una collections.deque como cola.
    • Si obtener el más antiguo no es tan importante, puede utilizar el método popitem para eliminar un elemento arbitrario.
  • Interpreté el más antiguo para significar la primera inserción, aproximadamente. Tendrías que hacer algo un poco diferente para eliminar los elementos LRU. La estrategia eficiente más obvia consistiría en mantener una lista de claves doblemente enlazada con referencias a los nodos almacenados como valores dict (junto con los valores reales). Esto se vuelve más complicado y su implementación en Python puro conlleva muchos gastos generales.

Puede crear una clase de diccionario personalizada por subclasificación de dict. En su caso, tendría que anular __setitem__ para verificar su propia longitud y eliminar algo si el límite se reduce. El siguiente ejemplo imprimirá la longitud actual después de cada inserción:

 class mydict(dict): def __setitem__(self, k, v): dict.__setitem__(self, k, v) print len(self) d = mydict() d['foo'] = 'bar' d['bar'] = 'baz' 

Ha habido muchas buenas respuestas, pero quiero señalar una implementación pythonic simple para el caché LRU. Es similar a la respuesta de Alex Martelli.

 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)