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




2 Answers

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

Sie sind Insertion bestellt [1] . Ab Python 3.6 erinnern Wörterbücher für die CPython-Implementierung von Python an die Reihenfolge der eingefügten Elemente . Dies wird als Implementierungsdetail in Python 3.6 betrachtet . Sie müssen OrderedDict wenn Sie die Reihenfolge der Einfügung erhalten möchten, die in anderen Implementierungen von Python (und anderen geordneten Verhalten [1] ) garantiert ist .

Ab Python 3.7 ist dies kein Implementierungsdetail mehr, sondern wird zu einem Sprachfeature. guaranteed :

Mach es so. "Dict behält die Reihenfolge der Anzeigen" ist das Urteil. Vielen Dank!

Das bedeutet einfach, dass Sie sich darauf verlassen können . Andere Implementierungen von Python müssen auch ein insertionsorientiertes Dictionary bieten, wenn sie eine konforme Implementierung von Python 3.7 sein wollen.

Wie funktioniert die Python 3.6 Wörterbuchimplementierung besser als die ältere, während die Reihenfolge der Elemente erhalten bleibt?

Im Wesentlichen, indem zwei Arrays beibehalten werden .

  • Das erste Array, dk_entries , enthält die Einträge ( vom Typ PyDictKeyEntry ) für das Wörterbuch in der Reihenfolge, in der sie eingefügt wurden. Die Erhaltung der Ordnung wird dadurch erreicht, dass es sich um ein nur anhängiges Array handelt, bei dem immer neue Elemente am Ende eingefügt werden (Einfügereihenfolge).

  • Die zweite, dk_indices , enthält die Indizes für das Array dk_entries ( dk_entries Werte, die die Position des entsprechenden Eintrags in dk_entries ). Dieses Array fungiert als Hash-Tabelle. Wenn ein Schlüssel gehashed wird, führt er zu einem der Indizes, die in dk_indices gespeichert dk_indices und der entsprechende Eintrag wird durch Indexieren von dk_entries . Da nur Indizes beibehalten werden, hängt der Typ dieses Arrays von der Gesamtgröße des Wörterbuchs ab (vom Typ int8_t ( 1 Byte) bis int32_t / int64_t ( int64_t Byte) bei 32 / 64 Bit-Builds)

In der vorherigen Implementierung musste ein Sparse-Array vom Typ PyDictKeyEntry und der Größe dk_size zugewiesen werden. Leider führte dies auch zu einer Menge Leerraum, da dieses Array aus Leistungsgründen nicht mehr als 2/3 * dk_size voll sein durfte . (und der leere Speicherplatz hatte immer noch PyDictKeyEntry Größe!).

Dies ist jetzt nicht der Fall, da nur die erforderlichen Einträge gespeichert werden (diejenigen, die eingefügt wurden) und ein Sparse-Array vom Typ intX_t ( X abhängig von der intX_t ) 2/3 * dk_size s full wird beibehalten. Der leere Bereich wurde vom Typ PyDictKeyEntry in intX_t .

PyDictKeyEntry ist das Erstellen eines spärlichen Arrays vom Typ PyDictKeyEntry viel mehr Speicher PyDictKeyEntry als ein sparse Array zum Speichern von int s.

Sie können die vollständige Konversation mail.python.org/pipermail/python-dev/2016-September/146327.html Bezug auf dieses Feature sehen, wenn Sie interessiert sind, es ist ein gutes Buch.

In dem ursprünglichen Vorschlag von Raymond Hettinger ist eine Visualisierung der verwendeten Datenstrukturen zu sehen, die den Kern der Idee einfängt.

Zum Beispiel das Wörterbuch:

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

ist momentan gespeichert als:

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

Stattdessen sollten die Daten wie folgt organisiert sein:

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

Wie Sie sehen können, ist im ursprünglichen Vorschlag viel Platz im Wesentlichen leer, um Kollisionen zu reduzieren und das Nachschlagen zu beschleunigen. Mit dem neuen Ansatz reduzieren Sie den Speicherbedarf, indem Sie die Spärlichkeit in den Indizes dorthin verschieben, wo sie wirklich benötigt wird.

[1]: Ich sage "Insertion ordered" und nicht "ordered", da "Ordered" mit der Existenz von OrderedDict auf weiteres Verhalten hindeutet, das das dict Objekt nicht bietet . OrderedDicts sind reversibel, stellen auftragsorientierte Methoden zur Verfügung und bieten vor allem ordersensitive Gleichheitsprüfungen ( == ,! != ). dict s bietet derzeit keine dieser Verhaltensweisen / Methoden an.

[2]: Die neuen Wörterbuchimplementierungen funktionieren besser im Speicher, indem sie kompakter gestaltet werden; das ist der Hauptvorteil hier. Geschwindigkeit ist der Unterschied nicht so drastisch, es gibt Orte, wo das neue Diktat leichte Regressionen einführen könnte ( Key-Lookups zum Beispiel ), während in anderen (Iteration und Größenanpassung in den Sinn kommen) eine Leistungssteigerung vorhanden sein sollte.

Insgesamt verbessert sich die Leistungsfähigkeit des Wörterbuchs, insbesondere in realen Situationen, aufgrund der eingeführten Kompaktheit.

lines matplotlib

Wörterbücher sind in Python 3.6 (zumindest unter der CPython-Implementierung) angeordnet, anders als in früheren Inkarnationen. Dies scheint eine wesentliche Änderung zu sein, aber es ist nur ein kurzer Abschnitt in der documentation . Es wird eher als CPython-Implementierungsdetail als als Sprachfeature beschrieben, bedeutet aber auch, dass dies in Zukunft Standard werden kann.

Wie funktioniert die neue Wörterbuchimplementierung besser als die ältere, während die Reihenfolge der Elemente erhalten bleibt?

Hier ist der Text aus der Dokumentation:

dict() jetzt eine "kompakte" Darstellung, die von PyPy entwickelt wurde . Die Speicherbelegung des neuen dict () ist im Vergleich zu Python 3.5 um 20% bis 25% kleiner. 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 verlässlich sein (dies kann sich in der Zukunft ändern, aber es ist wünschenswert, diese neue dict-Implementierung in der Sprache für einige Versionen zu haben, bevor die Sprachspezifikation geändert wird Ordnungskonservierende Semantik für alle aktuellen und zukünftigen Python-Implementierungen vorschreiben, was auch die Rückwärtskompatibilität mit älteren Versionen der Sprache, in denen die zufällige Iterationsreihenfolge noch immer gültig ist (zB Python 3.5), erhält. (Beitrag von INADA Naoki in Heft 27350. Idee ursprünglich von Raymond Hettinger vorgeschlagen .)

Update Dezember 2017: dict 's Beibehaltung der Reihenfolge ist für Python 3.7 guaranteed




Update: Guido van Rossum guaranteed dass ab Python 3.7 in allen Python-Implementierungen die Reihenfolge der Einfügungen beibehalten werden muss.




Related

python python-3.x dictionary python-internals python-3.6