Wie beschränken Sie die Größe von einem Wörterbuch?

Ich würde gerne mit ein dict in python, aber begrenzen die Anzahl der Schlüssel/Wert-Paare zu X. In anderen Worten, wenn die dict-ist derzeit die Speicherung von X Schlüssel/Wert-Paaren und ich führen eine insertion, möchte ich einen der vorhandenen Paare gelöscht werden. Es wäre schön, wenn es wurde vor kurzem die wenigsten eingefügt/greift auf die Taste, aber das ist nicht wirklich notwendig.

Falls vorhanden in der standard-Bibliothek bitte erspart mir einige Zeit und richten Sie es aus!

  • duplizieren: stackoverflow.com/questions/1756992/...
  • gute zu finden. ich möchte, um diese herum aber da ich nicht speziell lru.
  • Die Begrenzung der Größe scheint genug von einer Unterscheidung zu einer anderen Frage, aber ja, die Frage ist die Hälfte dieses.
InformationsquelleAutor anthony | 2010-03-13
  1. 41

    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)

    Würden Sie auch überschreiben müssen andere Methoden, die Elemente einfügen, wie update. Der primäre nutzen von OrderedDict ist, so dass Sie kontrollieren können, was bekommt knallte leicht, ansonsten eine normale dict funktionieren würde.

    • size_limit=None, *args, **kwds) ist falsch und keyword-only-Parameter ((self, *args, size_limit=None, **kwds)) sind nicht in der aktuellen 2.x. (Werden Sie als für 2.7? Unabhängig sind Sie nicht 2.6.) Dieser code funktioniert mit fast jeder version der OP ist wahrscheinlich zu verwenden, macht size_limit effektiv ein Schlüsselwort-parameter nur, und hält die gleiche Schnittstelle wie dicts.
    • Haben Sie getestet, der code auf Python 2.7? dict.pop erfordert mindestens 1 argument. dict.popitem() funktioniert, aber es entfernt das aktuelle Element.
    • Auch setitem sollte geprüft werden, ob die Größe begrenzen, bevor eigentlich die Einstellung der Artikel, damit Sie nicht am Ende verlieren die sehr Element sind!
    • Betrachtet man es nun, Monate später, ich bin mir nicht sicher, was ich dachte; aber popitem mehr Sinn macht.
    • Sie müssen überprüfen Sie nach dem einstellen der Ware, wie Sie sein könnte, ersetzt ein bereits vorhandenes Element.
    • Um genau zu sein, das ist nicht wirklich ein LRU-Implementierung. Dies ist FIFO mit Löschung aus dict-Größe Begrenzung. Um eine voll-LRU-Implementierung, man muss überschreiben __contains__ - Methode verschieben Sie den letzten Punkt "verwendet" oder abgefragt, um die Spitze der dict-Link-Liste. [Ich verstehen, obwohl das nicht das Hauptziel ist die Frage]
    • Ich denke, diese Antwort ist viel zu hoch bewertet, da es nicht zeigen, wie zu implementieren, die mit anderen Methoden wahrscheinlich auch erforderlich werden, bedürfen gehören nicht nur diejenigen, die hinzufügen/einfügen von Elementen wie der Autor erwähnt, sondern auch alle, löschen/entfernen Sie Sie.

    InformationsquelleAutor
  2. 17

    cachetools bieten Ihnen schöne Umsetzung der Zuordnung des Hashes, die diese (und es funktioniert auf python 2 und 3).

    Auszug aus der Dokumentation:

    Für den Zweck dieses Moduls, ein cache ist eine veränderliche Zuordnung einer festen
    maximale Größe. Wenn der cache voll ist, d.h. durch hinzufügen weiterer Artikel die
    cache würde die Maximalgröße überschritten wird, muss der cache entscheiden, welches Element(s)
    zu verwerfen, die basierend auf einem geeigneten cache-Algorithmus.

    InformationsquelleAutor vaab
  3. 10

    Hier ist eine einfache, no-LRU-Python 2.6+ - Lösung (in älteren Pythons, die Sie tun könnten, etwas ähnliches mit UserDict.DictMixin, aber in 2.6 und besser, es wird nicht empfohlen, und das ABC von collections vorzuziehen sind 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))

    Anderen Antworten erwähnt, werden Sie wahrscheinlich nicht wollen, um eine Unterklasse dict -- die explizite delegation self.d ist leider boilerplatey aber es hat Garantie, dass jede andere Methode ist ordnungsgemäß geliefert collections.MutableMapping.

    InformationsquelleAutor Alex Martelli
  4. 8

    Hier ist eine einfache und effiziente LRU-cache geschrieben, mit Schmutz einfache 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))
    • wow, du schreibst ziemlich viel LRU in so kurzer Zeit für verschiedene Benutzer Fällen ist es immer eine Freude zu Lesen, Ihre Python-code aus, ob python cookbook(activestate), python-standard-lib, blog -, twitter-oder pycon vorlesungen, und jetzt auf stackoverflow zu.
    • Diese Implementierung sieht nicht pythonic. Warum nicht OrderedDict und MutableMapping dies zu tun...
    • Es ist perfekt Pythonic -- eine einfache Klasse mit straight-forward-Nutzung der Wörterbücher, - Listen, - grundlegende Aufgaben eines Auspacken. Die Logik ist in sich abgeschlossen und es sind keine externen Abhängigkeiten. Dieser code ist auch sehr schnell und ist leicht weiter optimiert durch PyPy. Ein OrderedDict fügt Speicherplatz-overhead (es verwendet zwei dicts intern, während dieser nur eine), und es gibt unnötige Arbeit, die nicht notwendig für diesen Einsatz. MutableMapping nicht nützliche Funktionen in diesem Kontext.
    • Was ist der Punkt, der die Klasse-level-Definitionen von PREV, NEXT, KEY, und VALUE da Sie nicht in einer der Methoden?
    • Es ist dort einfach nur zeigen, die Struktur der Verknüpfung.
    InformationsquelleAutor Raymond Hettinger
  5. 2

    Einen dict-nicht dieses Verhalten haben. Sie machen Ihre eigene Klasse, der dies tut, zum Beispiel 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 Hinweise zu diesem

    • Würde es verlockend sein, für einige Unterklasse dict hier. Sie kann technisch, aber es ist Fehler-anfällig, weil die Methoden nicht voneinander abhängen. Sie können UserDict.DictMixin zu speichern, zu definieren, alle Methoden. Es gibt nur wenige Methoden, die Sie wäre in der Lage, wieder zu verwenden, wenn Sie eine Unterklasse dict.
    • Ein dict nicht weiß, was die zuletzt hinzugefügte Schlüssel ist, denn dicts sind ungeordnet.
      • 2.7 einführen collections.OrderedDict, aber für jetzt, halten Sie die Tasten, um separat funktionieren soll (verwenden Sie eine collections.deque als Warteschlange).
      • Wenn immer die ältesten nicht alle, die wichtige, können Sie einfach die popitem Methode zum löschen eines beliebigen Elements.
    • Ich interprettered ältesten zu meinen ersten einfügen, etwa. Sie hätte etwas tun, etwas anders zu beseitigen, die LRU-Elemente. Der offensichtlichste effiziente Strategie würde bedeuten, halten eine doppelt verknüpfte Liste der Schlüssel, mit verweisen auf die Knoten selbst gespeichert, als dict-Werte (zusammen mit den realen Werten). Dies wird komplizierter, und der Umsetzung in reinem Python hat eine Menge overhead.
    • Sie brauchen eigentlich etwas viel komplexeres als ein dict+deque, wenn Sie wollen, O(1) get-/set-/delitem, obwohl dies natürlich nur die es wirklich ankommt, für größere Größen.
    • Sie können direkt wiederverwenden, etwa die Hälfte der Methoden aus dem dict, OrderedDict oder andere base auch ohne DictMixin. Es ist wirklich nicht scheinen, die bugprone zu schreiben forwarding-Methoden für die anderen, sicherlich nicht mehr bugprone, als zu schreiben Sie alle selbst, als Sie hier haben.
    • Ich versuche zu bekommen, was hoffentlich löst das problem auf der hand. dict+deque gibt Sie O(1) get, set, und delitem wenn Sie nur ein wenig sorgen über die orderedness der Schlüssel, und Sie nicht fallen in dem pathologischen Fall, wo es viele Löschungen und erneuten Einstellung der gleichen Tasten, die zu den führenden deque verunreinigt wird, die durch Tasten nicht im dict.
    • Nein, für delitem Sie haben auf der Suche nach deque für das gelöschte Element, und das ist O(n). Check out eines der pure-Python OrderedDict Implementierungen.
    • Die Mehrheit der Male, die ich gesehen habe dict Unterklassen in der wildnis, die coder vergessen zu überschreiben die entsprechenden Methoden. Dies bedeutet, dass Fehler, die sich aus dieser die Möglichkeit haben, übergeben Sie still, das ist wirklich schlecht. Ich sehe wirklich nicht viel zu sein gewonnen von Unterklassen in einem Fall wie diesem.
    • Also überlegen Sie, was Sie tun, und schreiben Sie einige tests, die gleichen wie beim schreiben nichts. Schlampiger code wird immer Fehler haben.
    • Wenn Sie wollten, dass die aktuellen Schlüssel gespeichert, Sie würde haben auf der Suche nach deque oder list oder was auch immer. Allerdings, wenn Sie das Element da ist und wenn Sie es pop zu überprüfen, ob es im dict haben, speichern Sie die Suche. Ob diese skaliert oder nicht, hängt davon ab, wie die Instanzen verwendet werden.
    • Wie gesagt, ich sehe nicht viel Vorteil Unterklassen hier, um mit zu beginnen. Ich glaube nicht, dass es endet Einführung in die Gefahr—Dinge, die Aussehen wie Sie sollte die Arbeit und das würde arbeiten, wenn Unterklassen einer Python-Klasse wird nicht funktionieren. Ich würde sehen müssen, wirklichen nutzen zu wollen, vorstellen, dass so etwas wie code ich wurde Aufrechterhaltung der.
    • Vorausgesetzt, update-Aufrufe von getitem ohne wissen oder Prüfung ist schlampig jeder Weg Sie Scheibe es, und diese Annahme ist die einzige Weise, "wie [es] sollte funktionieren". Man weiß nie, wenn Sie fehlende Funktionen oder nicht , wenn Sie testen, oder sonst beweisen Sie alles, was Sie wollen, zu gewährleisten. - Wieder Blick auf die anständige pure-Python OrderedDict-Implementierungen, von denen es O(1) delitem.
    • Löschen der Schlüssel aus der linken Seite der deque und dabei einige Korrektheit, ich bin nicht unbedingt die Durchführung einer O(n) operation zum löschen der Elemente beseitigt werden.
    • "2.7 einführen Sammlungen.OrderedDict" Python 3.1 bereits OrderedDict. Zeit für eine Veränderung ?
    • Sehr, sehr wenige Menschen sind mit 3.x für das schreiben ernst-code, die derzeit wegen der mangelnden Unterstützung durch wichtige Bibliotheken wie numpy, PIL, verdreht, und die meisten web-frameworks und wegen der Kosten der Portierung von code-Basen. (Besonders die ersteren Grund.)
    • Wenn ich sage, delitem, ich meine __delitem__ wie in del d[key]. Hinweis: dies O(n) Suche wirklich egal, wenn er will verwenden LRU statt der LR-Hinzugefügt.
    • 3.x ist ein split von 2.x und Entwicklung geschieht parallel mit 2.x anstatt 3.x als "später". Ist es richtig zu sagen, 2.7 und 3.1, die beide die Einführung zu Ihren jeweiligen Linien.
    • Ich habe nicht definiert, was muss ich tun für Sie, dass der Betrieb, wenn OP braucht es überhaupt nicht. Sie haben noch zu tun, die O(n) Suche/löschen auf der deque/Liste, wenn Sie nicht müssen um einen container der aktuelle Schlüssel wie Sie muss in einem geordneten dict-Typ.
    • ich bin völlig dieser Tatsache bewusst sein. ich versuche nur zu überzeugen, die meisten Menschen wechseln zu python 3.
    • weil Bibliotheken fehlen die python-3-Unterstützung, die Menschen verwenden Sie es nicht für ernsthafte Entwicklung, und wir sind wieder am Ausgangspunkt. wenn wir weiter diesen Weg, Menschen werden immer noch mit python 2 in 20 Jahren (wie die Menschen sind immer noch mit C89 heute).
    • Die (nicht-ganz-so-scary -) Bedrohung des Menschen kleben mit Python 2 auf lange Sicht nicht wechseln mehr möglich ist, für Menschen, die brauchen eine effiziente numerische Mathematik-Bibliothek, ein web-framework, eine tolle asynchrone Netzwerk-Bibliothek, oder ein Weg, um Bilder zu manipulieren.

    InformationsquelleAutor Mike Graham
  6. 1

    Können Sie erstellen ein benutzerdefiniertes Wörterbuch, indem bilden von Unterklassen der Klasse dict. In Ihrem Fall, müssten Sie überschreiben __setitem__ haben, überprüfen Sie Ihre eigenen Länge und etwas löschen, wenn das limit ist recahed. Das folgende Beispiel druckt die aktuelle Länge nach jedem einfügen:

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

d = mydict()
d['foo'] = 'bar'
d['bar'] = 'baz'
    • Unterklassen gelieferten wie dict ist oft fruchtlos. In normalen Umständen mit Unterklassen, Methoden wie update und setdefault verlassen würde, auf der overrided __getitem__, aber das ist nicht, wie es hier funktioniert. Unterklassen gelieferten lässt es sich leicht einführen, schwierig-zu-sehen-bugs. Wenn Sie beseitigen solche Fehler, die Sie wirklich nicht gespeichert habe jede Arbeit, die von Unterklassen.
    • Interessant. Sie konnten zeigen ein Beispiel für einen solchen Fehler?
    InformationsquelleAutor c089
  7. 1

    Es gab viele gute Antworten, aber ich möchte darauf hinweisen, eine einfache, pythonic Umsetzung für die LRU-cache. Es ist ähnlich wie Alex Martelli ' s 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)
    InformationsquelleAutor Ian Chen
Schreibe einen Kommentar