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

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

Sind Sie insertion bestellt^[1]. Wie in der Python-3.6, für die CPython-Implementierung von Python, Wörterbücher erinnere mich an die Reihenfolge der Elemente eingefügt. Dies wird als eine Implementierung detail in Python-3.6; Sie verwenden müssen OrderedDict wenn Sie möchten, dass die insertion der Bestellung, dass die garantiert über andere Implementierungen von Python (und anderen bestellten Verhalten^[1]).

Als Python-3.7, ist dies nicht mehr ein Implementierungsdetail und stattdessen wird ein Sprach-feature. Von einem python-dev Nachricht von GvR:

Machen es so. "Dict hält insertion order" ist die Entscheidung. Danke!

Dies bedeutet einfach, dass darauf kann man sich verlassen. Andere Implementierungen von Python muss auch bieten eine insertion bestellt, Wörterbuch, wenn Sie es wünschen, um eine konforme Implementierung der Python-3.7.

Wie funktioniert das Python - 3.6 Wörterbuch Umsetzung führen Sie besser^[2] als die älteren, während die Erhaltung element, um?

Im wesentlichen durch den halten zwei arrays.

• Dem ersten array, dk_entries, hält der Einträge (der Typ PyDictKeyEntry) das Wörterbuch in der Reihenfolge, wie Sie eingefügt wurden. Erhaltung der Ordnung wird erreicht, indem das eine append only-array, wobei neue Elemente immer eingesetzt am Ende (insertion order).

• Zweiten, dk_indices, hält die Indizes für die dk_entries array (das heißt, Werte, die angeben, dass die position des entsprechenden Eintrags in dk_entries). Dieses array dient als der hash-Tabelle. Wenn ein Schlüssel gehasht ist es führt zu einer der Indizes gespeichert in dk_indices und der entsprechende Eintrag wird abgerufen durch die Indizierung dk_entries. Da werden nur die Indizes gehalten werden, der den Typ dieses Arrays hängt von der Gesamt Größe des dictionary (im Bereich von Typ int8_t(1 byte) int32_t /int64_t (4/8 bytes) 32 /64 bit-builds)

In der vorherigen Implementierung, eine sparse-array vom Typ PyDictKeyEntry und Größe dk_size zugeordnet werden musste; leider ist es auch zu viel leerer Platz, da das array nicht erlaubt war, mehr zu sein als 2/3 * dk_size voll aus performance-Gründen. (und den leeren Raum noch hatte PyDictKeyEntry Größe!).

Dies ist nicht der Fall, da nur die erforderlich Einträge gespeichert sind (diejenigen, die eingefügt wurden) und ein sparse-array vom Typ intX_t (X je nach dict-Größe) 2/3 * dk_sizes voll gehalten wird. Der leere Raum geändert von Typ PyDictKeyEntry zu intX_t.

Also offensichtlich, die Schaffung eines sparse-Arrays des Typs PyDictKeyEntry ist viel mehr Speicher fordern als ein sparse-array für die Speicherung ints.

Können Sie sehen, das ganze Gespräch auf Python-Dev über diese Funktion, wenn Sie interessiert sind, ist es gut zu Lesen.

In dem ursprünglichen Vorschlag von Raymond Hettinger, eine Visualisierung von Datenstrukturen, die verwendet werden können, gesehen, erfasst den Kern der Idee.

Zum Beispiel, das Wörterbuch:

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

derzeit gespeichert:

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

Stattdessen sollten die Daten werden wie folgt organisiert:

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

So können Sie visuell sehen jetzt, in der ursprüngliche Vorschlag, eine Menge Platz ist im wesentlichen leer zu reduzieren Kollisionen und machen look-ups schneller. Mit dem neuen Konzept, reduzieren Sie den Speicherbedarf durch verschieben der Kargheit, wo es wirklich erforderlich, in den Indizes.

_{[1]: ich sage "insertion bestellt" und nicht "bestellt", da mit der Existenz von OrderedDict, "bestellt", schlägt weiter Verhalten, dass die dict Objekt nicht. OrderedDicts reversibel sind, bieten, um sensible Methoden und, vor allem, bieten Sie eine um-sensive Gleichheit tests (==, !=). dicts derzeit bieten keine dieser Verhaltensmuster/- Methoden.}

_{[2]: Der neue Wörterbuch-Implementierungen bessere Speicher weisen durch mehr entwickelt, kompakt; das ist der größte Vorteil hier. Geschwindigkeit klug, der Unterschied ist nicht so drastisch, es gibt Orte, wo das neue dict führen könnten leichte Regressionen ( Schlüssel-lookups, zum Beispiel ), während in anderen (iteration und Größenänderung in den Sinn kommen) eine Leistungssteigerung vorhanden sein sollten.}

_{Insgesamt ist die Leistung des Wörterbuches, vor allem in real-life-Situationen, verbessert aufgrund der Kompaktheit eingeführt.}

InformationsquelleAutor Jim Fasarakis Hilliard

Update:
Guido van Rossum angekündigt auf der mailing-Liste , wie der Python-3.7 dicts in allen Python-Implementierungen müssen bewahren, insertion um.

InformationsquelleAutor fjsj