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

Question

Me gustaría trabajar con un diccionario en Python, pero limitar el número de pares clave / valor de X. En otras palabras, si el dict está almacenando pares clave X / valor y realizar una inserción, lo haría como uno de los pares existentes que se retiren. Sería bueno si era la menos recientemente insertado / accede clave, pero eso no es completamente necesario.

Si esto existe en la biblioteca estándar por favor me ahorrar algo de tiempo y señalarlo!

Answer 1

Python 2.7 y 3.1 tienen OrderedDict y hay implementaciones puras-Python para pitones 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)

Se podría también tener que reemplazar otros métodos que se pueden insertar elementos, tales como update. El uso principal de OrderedDict es para que pueda controlar lo que se metió con facilidad, por lo demás un dict normal sería trabajar.

Answer 2

cachetools le proporcionará buena aplicación de la cartografía hashes que hace esto (y funciona en python 2 y 3).

Extracto de la documentación:

  

A los efectos de este módulo, una memoria caché es un mapeo de un mutable fijo   talla máxima. Cuando la caché está llena, es decir, añadiendo otro elemento de la   caché excedería su tamaño máximo, el caché debe elegir qué elemento (s)   para descartar basado en un algoritmo de caché adecuado.

Answer 3

Esto es un simple, no-LRU solución Python 2.6+ (en pitones de edad avanzada se podría hacer algo similar con UserDict.DictMixin, pero en 2.6 y mejor que no es recomendable, y el ABC de collections son preferibles 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 otras respuestas mencionadas, es probable que no quiere subclase dict - la delegación explícita a self.d Sentimos boilerplatey pero lo hace Garantía que todos los demás métodos se suministra adecuadamente por collections.MutableMapping

Answer 4

Este es un simple y eficiente caché LRU escrita con un simple código Python suciedad 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 5

A dict no tiene este comportamiento. Se 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 acerca de este

• Sería tentador para algunos subclase dict aquí. Se puede hacer técnicamente esto, pero es propenso a error debido a que los métodos no dependen unos de otros. Se puede utilizar para guardar UserDict.DictMixin tener que definir todos los métodos. Hay algunos métodos que sería capaz de reutilización si dict subclase.
• Una dict no sabe cuál es la clave menos recientemente añadido es, ya que predice no están ordenados.
  • 2.7 introducirá collections.OrderedDict, pero por ahora mantener las llaves con el fin separado debería funcionar bien (usar un collections.deque como una cola).
  • Si conseguir el más antiguo no es tan imporante, sólo se puede utilizar el método popitem eliminar un elemento arbitrario.
• I interprettered más antigua en el sentido de la primera inserción, aproximadamente. Usted tendría que hacer algo un poco diferente para eliminar los elementos LRU. La estrategia eficiente más obvia sería implicar el mantenimiento de una lista doblemente enlazada de llaves con referencias a los nodos mismos almacenan como valores dict (junto con los valores reales). Esto se vuelve más complicado y su implementación en Python puro lleva un montón de gastos.

Answer 6

Puede crear una clase de diccionario personalizado subclasificando dict. En su caso, se tendría que anular __setitem__ tener comprobar su propia longitud y borrar algo si se recahed el límite. El siguiente ejemplo imprimiría 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'

Answer 7

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