Limiter la taille d'un dictionnaire python

Question

J'aimerais travailler avec un dict en python, mais limiter le nombre de paires clé/valeur à X. En d'autres termes, si le dict stocke actuellement X paires clé/valeur et que j'effectue une insertion, je voudrais qu'une des paires existantes soit abandonnée. Ce serait bien si c'était la clé la moins récemment insérée/accédée, mais ce n'est pas complètement nécessaire.

Si cela existe dans la bibliothèque standard, faites-moi gagner du temps et indiquez-le !

Answer 1

Python 2.7 et 3.1 ont OrderedDict et il existe des implémentations purement Python pour les Python antérieurs.

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)

Il faudrait aussi surcharger d'autres méthodes qui peuvent insérer des éléments, comme update. L'utilisation principale de OrderedDict est de pouvoir contrôler facilement ce qui est inséré, sinon un dict normal fonctionnerait.

Answer 2

Voici une solution simple, sans LRU, pour Python 2.6+ (dans les Python plus anciens, vous pouviez faire quelque chose de similaire avec UserDict.DictMixin mais dans les versions 2.6 et supérieures, ce n'est pas recommandé, et l'ABC de collections sont de toute façon préférables...) :

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 n'avez probablement pas envie de sous-classer dict - la délégation explicite à self.d est malheureusement très compliquée, mais elle permet d'atteindre les objectifs suivants garantie que toute autre méthode est correctement fournie par collections.MutableDict .

Answer 3

Voici un cache LRU simple et efficace écrit avec un simple code Python qui fonctionne sur n'importe quelle version de Python 1.5.2 ou plus :

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 4

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 remarques à ce sujet

• Il serait tentant pour certains de sous-classer dict ici. Vous pouvez techniquement le faire, mais c'est sujet à des bogues car les méthodes ne dépendent pas les unes des autres. Vous pouvez utiliser UserDict.DictMixin pour éviter de devoir définir toutes les méthodes. Il y a peu de méthodes que vous pourrez réutiliser si vous sous-classez dict .
• Un dict ne sait pas quelle est la clé la moins récemment ajoutée, puisque les dicts ne sont pas ordonnés.
  • La version 2.7 introduira collections.OrderedDict mais pour l'instant, garder les clés dans l'ordre séparément devrait fonctionner correctement (utilisez un fichier collections.deque comme une file d'attente).
  • Si l'obtention de la plus ancienne n'est pas si importante, vous pouvez simplement utiliser la fonction popitem pour supprimer un élément arbitraire.
• J'ai interprété le terme "plus ancien" comme signifiant "première insertion", approximativement. Il faudrait faire quelque chose d'un peu différent pour éliminer les éléments LRU. La stratégie efficace la plus évidente consisterait à conserver une liste de clés doublement liées avec des références aux noeuds eux-mêmes stockés comme valeurs dict (avec les valeurs réelles). Cela devient plus compliqué et son implémentation en Python pur entraîne beaucoup de surcharge.

Answer 5

Vous pouvez créer une classe de dictionnaire personnalisée en sous-classant dict. Dans votre cas, vous devrez surcharger la classe __setitem__ de vérifier votre propre longueur et de supprimer quelque chose si la limite est dépassée. L'exemple suivant affiche 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'