Sind Wörterbücher in Python 3.6+ bestellt?

Wörterbücher sind ab Python 3.6 in der Reihenfolge der Einfügung angeordnet. Es wird eher als CPython-Implementierungsdetail als als Sprachfunktion beschrieben. Das Dokumentation Zustände:

dict() verwendet nun eine „kompakte“ Darstellung Pionierarbeit von PyPy. Der Speicherverbrauch des neuen dict() ist zwischen 20 % und 25 % kleiner im Vergleich zu Python 3.5. PEP 468 (Beibehaltung der Reihenfolge von **kwargs in einer Funktion.) wird dadurch implementiert. Der ordnungserhaltende Aspekt dieser neuen Implementierung wird als Implementierungsdetail angesehen und sollte nicht als verlässlich angesehen werden (dies kann sich in Zukunft ändern, aber es ist wünschenswert, diese neue dict-Implementierung für einige Releases in der Sprache zu haben, bevor die Sprachspezifikation geändert wird um eine reihenfolgeerhaltende Semantik für alle aktuellen und zukünftigen Python-Implementierungen vorzuschreiben; dies trägt auch dazu bei, die Abwärtskompatibilität mit älteren Versionen der Sprache zu wahren, in denen noch eine zufällige Iterationsreihenfolge gilt, z. B. Python 3.5). (Beigetragen von INADA Naoki in Ausgabe 27350. Idee ursprünglich von Raymond Hettinger vorgeschlagen.)

Wie funktioniert die neue Wörterbuchimplementierung besser als die ältere, während die Elementreihenfolge beibehalten wird?

Update Dezember 2017: dicts Beibehaltung der Anzeigenreihenfolge ist garantiert für Python 3.7

Sind Wörterbücher in Python 3.6+ bestellt?

Sie sind Einfügung bestellt^[1].

Ab Python 3.6für die CPython-Implementierung von Python, Wörterbücher Merken Sie sich die Reihenfolge der eingefügten Elemente. Dies wird in Python 3.6 als Implementierungsdetail betrachtet; Sie müssen verwenden OrderedDict wenn Sie Insertion Ordering wollen, ist das so garantiert gegenüber anderen Implementierungen von Python (und anderem geordneten Verhalten^[1]).

Ab Python 3.7ist dies eine garantierte Sprachfunktion, nicht nur ein Implementierungsdetail. Aus einer Python-Dev-Nachricht von GvR:

Mach es so. „Dict hält Insertionsreihenfolge ein“, lautet das Urteil. Vielen Dank!

Das bedeutet einfach darauf kannst du dich verlassen. Andere Implementierungen von Python müssen ebenfalls ein Insertion Ordered Dictionary anbieten, wenn sie eine konforme Implementierung von Python 3.7 sein wollen.

Wie funktioniert die Python 3.6 Wörterbuchimplementierung performt besser^[2] als die ältere unter Beibehaltung der Elementreihenfolge?

Im Wesentlichen durch zwei Arrays halten.

• Das erste Array, dk_entriesenthält die Einträge (des Typs PyDictKeyEntry) für das Wörterbuch in der Reihenfolge, in der sie eingefügt wurden. Die Beibehaltung der Reihenfolge wird dadurch erreicht, dass es sich um ein Array nur zum Anhängen handelt, bei dem neue Elemente immer am Ende eingefügt werden (Einfügungsreihenfolge).

• Der Zweite, dk_indicesenthält die Indizes für die dk_entries array (d. h. Werte, die die Position des entsprechenden Eintrags in angeben dk_entries). Dieses Array fungiert als Hash-Tabelle. Wenn ein Schlüssel gehasht wird, führt er zu einem der darin gespeicherten Indizes dk_indices und der entsprechende Eintrag wird durch Indizierung geholt dk_entries. Da nur Indizes gespeichert werden, hängt der Typ dieses Arrays von der Gesamtgröße des Wörterbuchs ab (von type int8_t(1 Byte) zu int32_t/int64_t (4/8 Bytes) an 32/64 Bit baut)

In der vorherigen Implementierung ein Array mit geringer Dichte vom Typ PyDictKeyEntry und Größe dk_size musste zugeteilt werden; Leider führte dies auch zu viel leerem Platz, da dieses Array nicht größer als sein durfte 2/3 * dk_size voll aus Leistungsgründen. (und der leere Raum still hatte PyDictKeyEntry Größe!).

Dies ist jetzt nicht der Fall, da nur die erforderlich Einträge werden gespeichert (diejenigen, die eingefügt wurden) und ein spärliches Array des Typs intX_t (X je nach Diktgröße) 2/3 * dk_sizes voll bleibt. Der Leerraum hat sich vom Typ geändert PyDictKeyEntry zu intX_t.

Also offensichtlich ein spärliches Array von Typen erstellen PyDictKeyEntry ist viel speicherintensiver als ein Sparse-Array zum Speichern ints.

Sie können das vollständige Gespräch sehen auf Python-Dev In Bezug auf diese Funktion ist es bei Interesse eine gute Lektüre.

Im ursprünglichen Vorschlag von Raymond Hettingerist eine Visualisierung der verwendeten Datenstrukturen zu sehen, die den Kern der Idee erfasst.

Zum Beispiel das Wörterbuch:

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

wird derzeit gespeichert als [keyhash, key, value]:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

Stattdessen sollten die Daten wie folgt organisiert werden:

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

Wie Sie jetzt visuell sehen können, ist im ursprünglichen Vorschlag viel Platz im Wesentlichen leer, um Kollisionen zu reduzieren und Suchen schneller zu machen. Mit dem neuen Ansatz reduzieren Sie den erforderlichen Speicher, indem Sie die Sparseness dorthin verschieben, wo sie wirklich benötigt wird, in den Indizes.

_{[1]: Ich sage “Einfügung bestellt” und nicht “bestellt”, da “bestellt” mit der Existenz von OrderedDict ein weiteres Verhalten nahelegt, das das Objekt “dict” *nicht bereitstellt*. OrderedDicts sind reversibel, bieten reihenfolgeempfindliche Methoden und stellen hauptsächlich reihenfolgeempfindliche Gleichheitstests (`==`, `!=`) bereit. `dict`s bieten derzeit keine dieser Verhaltensweisen/Methoden an.}

_{[2]: Die neuen Wörterbuchimplementierungen funktionieren **speichertechnisch** besser, da sie kompakter gestaltet sind; das ist der Hauptvorteil hier. In Bezug auf die Geschwindigkeit ist der Unterschied nicht so drastisch, es gibt Stellen, an denen das neue Diktat leichte Regressionen einführen könnte (Key-Lookups, zum Beispiel), während in anderen (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.

Nachfolgend wird die ursprüngliche erste Frage beantwortet:

Sollte ich es benutzen dict oder OrderedDict in Python 3.6?

Ich denke, dieser Satz aus der Dokumentation reicht eigentlich aus, um Ihre Frage zu beantworten

Der ordnungserhaltende Aspekt dieser neuen Implementierung wird als Implementierungsdetail betrachtet und sollte nicht als verlässlich angesehen werden

dict ist nicht ausdrücklich als geordnete Sammlung gedacht, wenn Sie also konsistent bleiben und sich nicht auf einen Nebeneffekt der neuen Implementierung verlassen möchten, sollten Sie dabei bleiben OrderedDict.

Machen Sie Ihren Code zukunftssicher 🙂

Darüber gibt es eine Debatte hier.

BEARBEITEN: Python 3.7 behält dies als Feature bei sehen

Update: Guido van Rossum auf der Mailingliste angekündigt das ab Python 3.7 dicts in allen Python-Implementierungen müssen die Reihenfolge der Einfügung beibehalten.

Ich wollte zur obigen Diskussion beitragen, habe aber nicht den Ruf, einen Kommentar abzugeben.

Python 3.8 enthält die reversed() Funktion in Wörterbüchern (Entfernen eines weiteren Unterschieds aus OrderedDict.

Dict und dictviews können jetzt mit reversed() in umgekehrter Einfügereihenfolge iteriert werden. (Beigetragen von Rémi Lapeyre in bpo-33462.)
Sehen Sie, was es Neues in Python 3.8 gibt

Ich sehe keine Erwähnung des Gleichheitsoperators oder anderer Funktionen von OrderedDict sie sind also immer noch nicht ganz gleich.

Um diese Frage im Jahr 2020 vollständig zu beantworten, lassen Sie mich einige Aussagen zitieren offizielle Python-Dokumentation:

Geändert in Version 3.7: Die Wörterbuchreihenfolge ist garantiert die Reihenfolge der Einfügungen. Dieses Verhalten war ein Implementierungsdetail von CPython von 3.6.

Geändert in Version 3.7: Die Wörterbuchreihenfolge ist garantiert die Reihenfolge der Einfügungen.

Geändert in Version 3.8: Wörterbücher sind jetzt umkehrbar.

Wörterbücher und Wörterbuchansichten sind reversibel.

EIN Aussage bezüglich OrderedDict vs. Dict:

Geordnete Wörterbücher sind genau wie normale Wörterbücher, haben aber einige zusätzliche Funktionen in Bezug auf Bestellvorgänge. Sie haben an Bedeutung verloren, seit die eingebaute Klasse dict die Fähigkeit erlangt hat, sich die Reihenfolge der Einfügungen zu merken (dieses neue Verhalten wurde in Python 3.7 garantiert).