Wörterbücher werden in Python 3.6 (zumindest unter der CPython-Implementierung) anders als in früheren Inkarnationen bestellt. Dies scheint eine wesentliche Änderung zu sein, ist jedoch nur ein kurzer Absatz in der Dokumentation . Es wird eher als CPython-Implementierungsdetail als als Sprachfunktion beschrieben, impliziert jedoch auch, dass dies in Zukunft zum Standard werden kann.
Wie funktioniert die neue Wörterbuchimplementierung unter Beibehaltung der Elementreihenfolge besser als die ältere?
Hier ist der Text aus der Dokumentation:
dict()
Verwendet jetzt eine von PyPy entwickelte „kompakte“ Darstellung . Die Speichernutzung des neuen dict () ist im Vergleich zu Python 3.5 zwischen 20% und 25% geringer. PEP 468 (Beibehalten der Reihenfolge von ** kwargs in einer Funktion.) Wird dadurch implementiert. Der auftragserhaltende Aspekt dieser neuen Implementierung wird als Implementierungsdetail betrachtet und sollte nicht als verlässlich angesehen werden (dies kann sich in Zukunft ändern, es ist jedoch erwünscht, diese neue Dikt-Implementierung für einige Releases in der Sprache zu haben, bevor die Sprachspezifikation geändert wird Dies trägt auch dazu bei, die Abwärtskompatibilität mit älteren Versionen der Sprache zu gewährleisten, in denen die zufällige Iterationsreihenfolge noch gültig ist (z. B. Python 3.5). (Beitrag von INADA Naoki inAusgabe 27350 . Idee ursprünglich von Raymond Hettinger vorgeschlagen .)
Update Dezember 2017: Die dict
Beibehaltung der Einfügereihenfolge ist für Python 3.7 garantiert
quelle
**kwargs
und als solches ist der verwendete Wortlaut diplomatisch:**kwargs
In einer Funktionssignatur ist jetzt garantiert, dass es sich um eine Zuordnung handelt, die die Ordnungserhaltung einfügt . Sie haben den Begriff Mapping verwendet, um keine anderen Implementierungen zu zwingen, das Diktat zu ordnen (und einOrderedDict
internes zu verwenden) und um zu signalisieren, dass dies nicht von der Tatsache abhängen soll, dass dasdict
Diktat nicht geordnet ist.Antworten:
Sie sind Einfügungsreihenfolge [1] . Ab Python 3.6 merken sich Wörterbücher für die CPython-Implementierung von Python die Reihenfolge der eingefügten Elemente . Dies wird in Python 3.6 als Implementierungsdetail betrachtet . Sie müssen verwenden,
OrderedDict
wenn Sie eine Einfügereihenfolge wünschen, die für andere Implementierungen von Python (und anderes geordnetes Verhalten [1] ) garantiert ist .Ab Python 3.7 ist dies kein Implementierungsdetail mehr, sondern wird zu einer Sprachfunktion. Aus einer Python-Dev-Nachricht von GvR :
Dies bedeutet einfach, dass Sie sich darauf verlassen können . Andere Implementierungen von Python müssen ebenfalls ein Wörterbuch mit Einfügungsreihenfolge anbieten, wenn sie eine konforme Implementierung von Python 3.7 sein sollen.
Im Wesentlichen durch Beibehalten von zwei Arrays .
Das erste Array
dk_entries
enthält die Einträge ( vom TypPyDictKeyEntry
) für das Wörterbuch in der Reihenfolge, in der sie eingefügt wurden. Die Beibehaltung der Reihenfolge wird dadurch erreicht, dass dies ein Array nur zum Anhängen ist, in das immer neue Elemente am Ende eingefügt werden (Einfügereihenfolge).Die zweite
dk_indices
enthält die Indizes für dasdk_entries
Array (dh Werte, die die Position des entsprechenden Eintrags in angebendk_entries
). Dieses Array fungiert als Hash-Tabelle. Wenn ein Schlüssel gehasht wird, führt dies zu einem der darin gespeicherten Indizes,dk_indices
und der entsprechende Eintrag wird durch Indizierung abgerufendk_entries
. Da nur Indizes beibehalten werden, hängt der Typ dieses Arrays von der Gesamtgröße des Wörterbuchs ab (von Typint8_t
(1
Byte) bisint32_t
/int64_t
(4
/8
Byte) bei32
/64
Bit-Builds).In der vorherigen Implementierung musste ein spärliches Array von Typ
PyDictKeyEntry
und Größedk_size
zugewiesen werden. Leider führte dies auch zu viel leerem Speicherplatz, da dieses Array aus Leistungsgründen nicht mehr als2/3 * dk_size
voll sein durfte . (und der leere Raum noch hatte einePyDictKeyEntry
Größe!).Dies ist jetzt nicht der Fall, da nur die erforderlichen Einträge gespeichert werden (die eingefügt wurden) und ein spärliches Array vom Typ
intX_t
(X
abhängig von der Größe des Diktats)2/3 * dk_size
voll bleibt. Der leere Raum wurde von TypPyDictKeyEntry
zu geändertintX_t
.Das Erstellen eines spärlichen Arrays vom Typ
PyDictKeyEntry
ist daher viel speicherintensiver als ein spärliches Array zum Speichern vonint
s.Sie können die vollständige Konversation auf Python-Dev über diese Funktion sehen, wenn Sie interessiert sind, es ist eine gute Lektüre.
In dem ursprünglichen Vorschlag von Raymond Hettinger ist eine Visualisierung der verwendeten Datenstrukturen zu sehen, die den Kern der Idee erfasst.
Wie Sie jetzt visuell sehen können, ist im ursprünglichen Vorschlag im Wesentlichen viel Platz leer, um Kollisionen zu reduzieren und das Nachschlagen zu beschleunigen. Mit dem neuen Ansatz reduzieren Sie den erforderlichen Speicher, indem Sie die Spärlichkeit in den Indizes dorthin verschieben, wo sie wirklich benötigt wird.
[1]: Ich sage "Einfügung bestellt" und nicht "bestellt", da "bestellt" mit der Existenz von OrderedDict weiteres Verhalten nahe legt, das das
dict
Objekt nicht bereitstellt . OrderedDicts sind reversibel, bieten auftragssensitive Methoden und bieten hauptsächlich auftragssensitive Gleichheitstests (==
,!=
).dict
s bieten derzeit keine dieser Verhaltensweisen / Methoden an.[2]: Die neuen Wörterbuchimplementierungen bieten eine bessere Speicherleistung, da sie kompakter gestaltet sind. Das ist hier der Hauptvorteil. In Bezug auf die Geschwindigkeit ist der Unterschied nicht so drastisch. Es gibt Stellen, an denen das neue Diktat leichte Regressionen einführen kann ( z. B. Key-Lookups ), während in anderen Fällen (Iteration und Größenänderung) ein Leistungsschub vorhanden sein sollte.
Insgesamt verbessert sich die Leistung des Wörterbuchs, insbesondere in realen Situationen, aufgrund der eingeführten Kompaktheit.
quelle
entries
Wird die Größe der Liste geändert? oder wird ein Leerzeichen gehalten? oder wird es von Zeit zu Zeit komprimiert?DKIX_DUMMY
Wert von ersetzt-2
und der Eintrag imentry
Array durch ersetztNULL
. Wenn das Einfügen durchgeführt wird, werden die neuen Werte an das Eintragsarray angehängt. Es konnte noch nicht erkannt werden. aber ziemlich sicher, wenn die Indizes über den2/3
Schwellenwert hinaus gefüllt werden, wird eine Größenänderung durchgeführt. Dies kann dazu führen, dass vieleDUMMY
Einträge verkleinert werden, anstatt zu wachsen .d = {i:i for i in range(100)}
und Sie.pop
alle Elemente ohne Einfügen verwenden, ändert sich die Größe nicht. Wenn Sie es erneut hinzufügen,d[1] = 1
wird die entsprechende Größe berechnet und die Größe des Diktats geändert.dict
bestellt werden" zu entfernen ,dict
ist nicht in dem Sinne geordnet, wieOrderedDict
es ist. Das bemerkenswerte Problem ist die Gleichstellung.dict
s haben auftragsunempfindlich==
,OrderedDict
s haben auftragsempfindliche. Das Dumping vonOrderedDict
s und das Änderndicts
auf jetzt auftragsabhängige Vergleiche können zu einem erheblichen Bruch des alten Codes führen. Ich vermute, das einzige, was sich anOrderedDict
s ändern könnte, ist die Implementierung.Unten wird die ursprüngliche erste Frage beantwortet:
Ich denke, dieser Satz aus der Dokumentation reicht tatsächlich aus, um Ihre Frage zu beantworten
dict
ist nicht explizit als geordnete Sammlung gedacht. Wenn Sie also konsistent bleiben und sich nicht auf einen Nebeneffekt der neuen Implementierung verlassen möchten, sollten Sie dabei bleibenOrderedDict
.Machen Sie Ihren Code zukunftssicher :)
Es gibt eine Debatte darüber , dass hier .
EDIT: Python 3.7 hält dies als eine Funktion siehe
quelle
Update: Guido van Rossum kündigte auf der Mailingliste an, dass ab Python 3.7
dict
in allen Python-Implementierungen die Einfügereihenfolge beibehalten werden muss.quelle
move_to_end
Methode hat und seine Gleichheit auftragsabhängig ist: docs.python.org/3/library/… . Siehe den Hinweis zu Jim Fasarakis Hilliards Antwort.Ich wollte die obige Diskussion ergänzen, habe aber nicht den Ruf, einen Kommentar abzugeben.
Python 3.8 ist noch nicht ganz veröffentlicht, wird aber sogar die
reversed()
Funktion für Wörterbücher enthalten (wodurch ein weiterer Unterschied beseitigt wird)OrderedDict
.Ich sehe keine Erwähnung des Gleichheitsoperators oder anderer Merkmale von,
OrderedDict
so dass sie immer noch nicht ganz gleich sind.quelle