recorrer - Limitar el tamaño de un diccionario de Python

lista de diccionarios python

Question

Me gustaría trabajar con un dict en python, pero limitar el número de pares clave / valor a X. En otras palabras, si el dict almacena actualmente pares de clave / valor X y realizo una inserción, me gustaría uno de los pares existentes para ser eliminados. Sería bueno si fuera 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órreme un poco y señálelo!

Answer 1

Aquí hay un caché de LRU simple y eficiente escrito con un código simple de 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))

Answer 2

Aquí hay una solución simple, sin LRU Python 2.6+ (en versiones anteriores de Pythons podría hacer algo similar con UserDict.DictMixin , pero en 2.6 y mejor eso no es recomendable, y los ABC de las collections son preferibles 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 mencionaron otras respuestas, es probable que no desee subclasificar el dictado: la delegación explícita a self.d es, lamentablemente, repetitiva pero garantiza que los demás métodos son suministrados adecuadamente por collections.MutableDict .

Answer 3

Ha habido muchas buenas respuestas, pero quiero señalar una implementación pitthonic 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)

Answer 4

Puede crear una clase de diccionario personalizada subclasificando dict. En su caso, tendría que anular __setitem__ para verificar su propia longitud y eliminar algo si se vuelve a aplicar el límite. El siguiente ejemplo imprimirá la duración 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''

Answer 5

Python 2.7 y 3.1 tienen OrderedDict y hay 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 debería sobrescribir otros métodos que pueden insertar elementos, como la actualización. El uso principal de OrderedDict es para que pueda controlar lo que se salta fácilmente, de lo contrario funcionaría un dict normal.

Answer 6

Un dict no tiene este comportamiento. Podría hacer su propia clase que hace esto, por ejemplo, algo así 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 subclasificar el dict aquí. Técnicamente puedes hacer esto, pero es propenso a errores porque los métodos no dependen el uno del otro. Puede usar UserDict.DictMixin para ahorrar tener que definir todos los métodos. Hay pocos métodos que podría volver a utilizar si subclasifica dict .
• Un dict no sabe cuál es la clave añadida menos recientemente, ya que los dicts no están ordenados.
  • 2.7 introducirá collections.OrderedDict . collections.OrderedDict , pero por ahora mantener las claves en orden por separado debería funcionar bien (use una collections.deque como una cola).
  • Si obtener el más antiguo no es tan importante, puedes usar el método popitem para eliminar un elemento arbitrario.
• Interpreté la más antigua para significar la primera inserción, aproximadamente. Tendría que hacer algo un poco diferente para eliminar los elementos LRU. La estrategia eficiente más obvia implicaría 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 una gran sobrecarga.

Answer 7

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:

A los efectos de este módulo, un caché es un mapeo mutable de un tamaño máximo fijo. Cuando la memoria caché está llena, es decir, al agregar otro elemento, la memoria caché excedería su tamaño máximo, la memoria caché debe elegir qué elemento (s) desechar según un algoritmo de memoria caché adecuado.