Wie die Größe eines Wörterbuchs zu begrenzen?

Question

ich an der Arbeit mit einem dict in Python mochte, aber die Anzahl der Schlüssel / Wert-Paare X. Mit anderen Worten begrenzen, wenn die dict momentan X Schlüssel / Wert-Paare speichert und ich führe eine Insertion, würde ich wie eine der vorhandenen Paare fallen gelassen werden. Es wäre schön, wenn es die am wenigsten vor kurzem eingeführt / greift Schlüssel aber das ist nicht ganz notwendig.

ist

Wenn dies in der Standardbibliothek existiert bitte rette mich einige Zeit, und zeigen Sie es aus!

Answer 1

Python 2.7 und 3.1 haben OrderedDict und es gibt pure-Python-Implementierungen für frühere Pythons.

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)

Sie müßten auch andere Methoden außer Kraft setzen, die Elemente, wie update einfügen. Die primäre Verwendung von OrderedDict ist so können Sie steuern, was leicht geknallt bekommt, sonst ein normaler dict funktionieren würde.

Answer 2

cachetools wird Ihnen schöne Implementierung von Mapping Hashes, das dies tut (und es funktioniert auf Python 2 und 3).

Auszug aus der Dokumentation:

  

Für die Zwecke dieses Moduls ist ein Cache eine veränderbare Zuordnung eines festen   maximale Größe. Wenn der Cache voll ist, das heißt, durch ein anderes Element Hinzufügen der   Cache würde seine maximale Größe überschreiten, muss der Cache, welche Position (en) wählen   zu verwerfen, basierend auf einem geeigneten Cache-Algorithmus.

Answer 3

Hier ist eine einfache, nicht-LRU Python 2.6+ Lösung (in älteren Pythons Sie etwas ähnliches mit UserDict.DictMixin tun könnten, aber in 2.6 und besser, die nicht empfohlen wird, und die ABCs von collections bevorzugt sowieso ...):

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))

Wie andere Antworten erwähnt, werden Sie wahrscheinlich nicht wollen, zu Unterklasse dict - die explizite Delegation self.d leider boilerplatey ist, aber es tut Garantie , dass jede andere Methode von collections.MutableMapping richtig versorgt wird.

Answer 4

Hier ist eine einfache und effiziente LRU-Cache geschrieben mit Schmutz einfach Python-Code, läuft auf jedem Python-Version 1.5.2 oder höher:

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

Ein dict hat dieses Verhalten nicht. Sie könnten Ihre eigene Klasse machen, dass dies der Fall ist, zum Beispiel so etwas wie

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

Ein paar Anmerkungen zu diesem

• Es wäre hier für einige Unterklassen dict verlockend sein. Sie können dies technisch tun, aber es ist fehleranfällig, da die Methoden aufeinander nicht abhängen. Sie können UserDict.DictMixin verwenden, speichern Sie alle Methoden, die definieren. Es gibt nur wenige Methoden, die Sie können wiederverwendet werden würde, wenn Sie Unterklasse dict.
• A dict nicht weiß, was die am wenigsten kürzlich hinzugefügte Schlüssel ist, da dicts ungeordnet sind.
  • 2.7 wird collections.OrderedDict vorstellen, aber jetzt die Schlüssel, um zu halten separat sollte funktionieren (verwenden Sie einen collections.deque als Warteschlange).
  • Wenn immer die älteste ist nicht alles, was imporant, können Sie einfach die popitem Methode verwenden, ein beliebiges Element zu löschen.
• I interprettered älteste bis mittlere ersten Insertion, etwa. Sie müßten etwas ein wenig anders tun, um die LRU Elemente zu beseitigen. Die naheliegendste effiziente Strategie würde eine doppelt verknüpfte Liste von Schlüsseln mit Verweisen auf den Knoten selbst als dict Werte gespeichert zu halten (zusammen mit den realen Werten). Dies wird komplizierter und es in reiner Python Implementierung trägt eine Menge Aufwand.

Answer 6

Sie können eine benutzerdefinierten Wörterbuch Klasse erstellen, indem dict Subklassen. In Ihrem Fall würden Sie außer Kraft setzt __setitem__ müssen Sie Ihre eigene Länge überprüfen und etwas löschen, wenn die Grenze recahed wird. Das folgende Beispiel würde die aktuelle Länge nach jedem Einsetzen drucken:

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

Es gibt viele gute Antworten, aber ich möchte eine einfache, darauf hinzuweisen, pythonic Implementierung für LRU-Cache. Es ist ähnlich wie Alex Martelli Antwort.

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)