Como limitar o tamanho de um dicionário?

Question

Eu gostaria de trabalhar com um dicionário em python, mas limitar o número de pares de chave / valor para X. Em outras palavras, se o dict está actualmente a armazenar pares de chave / valor X e eu executar uma inserção, eu o faria como um dos pares existentes para ser descartado. Seria bom se fosse o menos recentemente inserido / acessa chave, mas isso não é absolutamente necessário.

Se isto existe na biblioteca padrão por favor, salve-me algum tempo e apontá-lo para fora!

Answer 1

Python 2.7 e 3.1 têm OrderedDict e há implementações 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)

Você também teria que substituir outros métodos que podem inserir itens, como update. O uso primário de OrderedDict é assim que você pode controlar o que é apareceu facilmente, caso contrário, um dict normais iria funcionar.

Answer 2

cachetools irá fornecer-lhe agradável implementação de mapeamento Hashes que faz isso (e ele funciona em python 2 e 3).

Trecho da documentação:

Para efeitos deste módulo, uma cache é um mapeamento mutável de um fixo tamanho máximo. Quando o cache estiver cheio, ou seja, adicionando outro item do esconderijo excedam o seu tamanho máximo, o cache deve escolher qual item (s) Para descartar baseado em um algoritmo de cache adequado.

Answer 3

Aqui está uma simples, sem LRU-Python 2.6+ solução (em Pythons mais velhos que você poderia fazer algo semelhante com UserDict.DictMixin, mas em 2,6 e melhor que não é recomendado, e os ABCs de collections são assim mesmo preferível ...):

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 outras respostas mencionado, você provavelmente não quer dict subclasse - a delegação explícita para self.d é, infelizmente, boilerplatey mas ele faz garantia que qualquer outro método é adequadamente fornecido pela collections.MutableMapping

Answer 4

Aqui é um simples e cache do LRU eficiente escrito com sujeira simples código Python que roda em qualquer versão python 1.5.2 ou 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 não tem esse comportamento. Você poderia fazer sua própria classe que faz isso, por exemplo, 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:
      ...

Algumas notas sobre este

• Seria tentador para alguns dict subclasse aqui. Você pode tecnicamente fazer isso, mas é bug-propensa porque os métodos não dependem uns dos outros. Você pode usar UserDict.DictMixin para salvar ter que definir todos os métodos. Existem alguns métodos que você seria capaz re-uso, se você subclasse dict.
• A dict não sabe o que a chave menos recentemente adicionado é, desde dicts são desordenadas.
  • 2.7 vai introduzir collections.OrderedDict, mas por agora manter as chaves, a fim separadamente deve funcionar bem (use um collections.deque como uma fila).
  • Se ficar o mais antigo não é tão imporant, você pode simplesmente usar o método popitem excluir um item arbitrário.
• I interprettered mais antiga para a primeira inserção média, aproximadamente. Você teria que fazer algo um pouco diferente para eliminar os itens LRU. A estratégia eficiente mais óbvia envolveria manter uma lista duplamente vinculada de chaves com referências para os nós-se armazenados como valores de dicionários (juntamente com os valores reais). Isto torna-se mais complicado e implementá-la em puro Python carrega um monte de sobrecarga.

Answer 6

Você pode criar uma classe de dicionário personalizado por subclasse dict. No seu caso, você teria que __setitem__ override ter verificar o seu próprio comprimento e excluir alguma coisa, se o limite for recahed. O exemplo a seguir iria imprimir o comprimento atual depois de cada inserção:

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

Houve muitas respostas boas, mas eu quero salientar um simples, implementação pythônico para o cache LRU. É semelhante a resposta 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)