Limiter la taille d'un dictionnaire python

Cachetools vous fournira une belle implémentation des hachages de mappage qui font cela (et cela fonctionne sur python 2 et 3).

Extrait de la documentation:

Aux fins de ce module, un cache est un mappage mutable d'un taille maximale. Lorsque le cache est plein, c'est à dire en ajoutant un autre élément de la le cache dépasser sa taille maximale, le cache doit choisir l'élément(s) à ignorer en fonction d'un algorithme de cache approprié.

Voici une solution simple et sans LRU python 2.6+ (dans les anciens Pythons, vous pouvez faire quelque chose de similaire avec UserDict.DictMixin, mais dans 2.6 et mieux ce n'est pas recommandé, et les ABC de collections sont préférables de toute façon...):

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)

Comme d'autres réponses l'ont mentionné, vous ne voulez probablement pas sous-classer dict - la délégation explicite à self.d est malheureusement boilerplatey mais il garantit que toutes les autres méthodes sont correctement fournies par collections.MutableDict.

Voici un cache LRU simple et efficace écrit avec du code Python simple dirt qui s'exécute sur n'importe quelle version python 1.5.2 ou ultérieure:

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 n'a pas ce comportement. Vous pouvez créer votre propre classe qui fait cela, par exemple quelque chose comme

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

Quelques notes à ce sujet

• Il serait tentant pour certains de sous-classer dict ici. Vous pouvez techniquement le faire, mais il est sujet aux bugs parce que les méthodes ne dépendent pas les unes des autres. Vous pouvez utiliser UserDict.DictMixin pour enregistrer la nécessité de définir toutes les méthodes. Il y a peu de méthodes que vous pourriez réutiliser si vous sous-classez dict.
• un dict ne sait pas ce que le la clé la moins récemment ajoutée est, puisque les dicts ne sont pas ordonnés.
  • 2.7 introduira collections.OrderedDict, mais pour l'instant garder les clés dans l'ordre séparément devrait fonctionner correctement (utilisez un collections.deque comme file d'attente).
  • Si obtenir le plus ancien n'est pas si important, vous pouvez simplement utiliser la méthode popitem pour supprimer un élément arbitraire.
• j'ai interprété le plus ancien comme signifiant la première insertion, approximativement. Vous devriez faire quelque chose d'un peu différent pour éliminer les éléments LRU. Le plus évident une stratégie efficace impliquerait de conserver une liste de clés doublement liée avec des références aux nœuds eux-mêmes stockées sous forme de valeurs dict (avec les valeurs réelles). Cela devient plus compliqué et l'implémenter en Python pur entraîne beaucoup de frais généraux.

Vous pouvez créer une classe de dictionnaire personnalisée en sous-classant dict. Dans votre cas, vous devrez remplacer __setitem__ pour vérifier votre propre longueur et supprimer quelque chose si la limite est recahée. L'exemple suivant imprimerait la longueur actuelle après chaque insertion:

class mydict(dict):
    def __setitem__(self, k, v):
        dict.__setitem__(self, k, v)
        print len(self)

d = mydict()
d['foo'] = 'bar'
d['bar'] = 'baz'

Il y a eu beaucoup de bonnes réponses, mais je veux souligner une implémentation pythonique simple pour le cache LRU. C'est similaire à la réponse D'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)