Zusammenfassung

Dieses PEP schlägt ein geordnetes Dictionary als neue Datenstruktur für das Modul collections vor, das in diesem PEP "OrderedDict" genannt wird. Die vorgeschlagene API integriert die Erfahrungen, die bei der Arbeit mit ähnlichen Implementierungen in verschiedenen realen Anwendungen und anderen Programmiersprachen gesammelt wurden.

Patch

Ein funktionierender Py3.1-Patch inklusive Tests und Dokumentation ist unter

OrderedDict Patch

Der Check-in erfolgte in den Revisionen: 70101 und 70102

Begründung

In aktuellen Python-Versionen gibt der weit verbreitete eingebaute dict-Typ keine Reihenfolge für die gespeicherten Schlüssel/Wert-Paare vor. Dies erschwert die Verwendung von Dictionaries als Datenspeicher für bestimmte Anwendungsfälle.

Einige dynamische Programmiersprachen wie PHP und Ruby 1.9 garantieren eine bestimmte Reihenfolge bei der Iteration. In diesen Sprachen und bestehenden Python-Implementierungen für geordnete Dictionaries wird die Reihenfolge der Elemente durch den Zeitpunkt der Einfügung des Schlüssels bestimmt. Neue Schlüssel werden am Ende angefügt, aber überschriebene Schlüssel werden nicht an das Ende verschoben.

Das folgende Beispiel zeigt das Verhalten bei einfachen Zuweisungen

>>> d = OrderedDict()
>>> d['parrot'] = 'dead'
>>> d['penguin'] = 'exploded'
>>> d.items()
[('parrot', 'dead'), ('penguin', 'exploded')]

Dass die Reihenfolge erhalten bleibt, macht ein OrderedDict in einigen Situationen nützlich

• XML/HTML-Verarbeitungsbibliotheken verwerfen derzeit die Reihenfolge von Attributen, verwenden eine Liste anstelle eines Dictionaries, was die Filterung umständlich macht, oder implementieren ihre eigenen geordneten Dictionaries. Dies betrifft ElementTree, html5lib, Genshi und viele weitere Bibliotheken.
• Es gibt viele Implementierungen von geordneten Dictionaries in verschiedenen Bibliotheken und Anwendungen, die meisten davon sind geringfügig inkompatibel miteinander. Darüber hinaus ist das Unterklasse von dict eine nicht triviale Aufgabe, und viele Implementierungen überschreiben nicht alle Methoden korrekt, was zu unerwarteten Ergebnissen führen kann.

  Zusätzlich sind viele geordnete Dictionaries ineffizient implementiert, was viele Operationen komplexer macht, als sie sein müssten.

• PEP 3115 erlaubt Metaklassen, das Mapping-Objekt für den Klassenrumpf zu ändern. Ein geordnetes Dictionary könnte verwendet werden, um geordnete Member-Deklarationen ähnlich wie C-Structs zu erstellen. Dies könnte zum Beispiel für zukünftige ctypes-Releases sowie für ORMs, die Datenbanktabellen als Klassen definieren, wie dasjenige, das das Django-Framework mitliefert, nützlich sein. Django verwendet derzeit einen hässlichen Hack, um die Reihenfolge der Member in Datenbankmodellen wiederherzustellen.
• Die Klasse RawConfigParser akzeptiert ein Argument dict_type, das es einer Anwendung ermöglicht, den intern verwendeten Dictionary-Typ festzulegen. Die Motivation für diese Ergänzung war ausdrücklich, Benutzern die Bereitstellung eines geordneten Dictionaries zu ermöglichen. [1]
• Code, der aus anderen Programmiersprachen wie PHP portiert wurde, hängt oft von einem geordneten Dictionary ab. Eine Implementierung eines ordnungsbewahrenden Dictionaries in der Standardbibliothek könnte den Übergang erleichtern und die Kompatibilität verschiedener Bibliotheken verbessern.

Ordered Dict API

Die API für geordnete Dictionaries wäre größtenteils mit dict und bestehenden geordneten Dictionaries kompatibel. Hinweis: Dieses PEP bezieht sich auf die Dictionary-API von 2.7 und 3.0, wie sie in der abstrakten Basisklasse collections.Mapping beschrieben ist.

Der Konstruktor und update() akzeptieren beide Iterables von Tupeln sowie Mappings, wie es ein dict tut. Im Gegensatz zu einem regulären Dictionary wird die Einfügungsreihenfolge beibehalten.

>>> d = OrderedDict([('a', 'b'), ('c', 'd')])
>>> d.update({'foo': 'bar'})
>>> d
collections.OrderedDict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])

Wenn geordnete Dictionaries aus regulären Dictionaries aktualisiert werden, ist die Reihenfolge neuer Schlüssel natürlich undefiniert.

Alle Iterationsmethoden sowie keys(), values() und items() geben die Werte zurück, geordnet nach dem Zeitpunkt, an dem der Schlüssel zuerst eingefügt wurde.

>>> d['spam'] = 'eggs'
>>> d.keys()
['a', 'c', 'foo', 'spam']
>>> d.values()
['b', 'd', 'bar', 'eggs']
>>> d.items()
[('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', 'eggs')]

Neue Methoden, die auf dict nicht verfügbar sind

OrderedDict.__reversed__()

Unterstützt die umgekehrte Iteration nach Schlüssel.

Fragen und Antworten

Was passiert, wenn ein vorhandener Schlüssel neu zugewiesen wird?

Der Schlüssel wird nicht verschoben, sondern an Ort und Stelle mit einem neuen Wert zugewiesen. Dies entspricht bestehenden Implementierungen.

Was passiert, wenn Schlüssel mehrmals in der an den Konstruktor übergebenen Liste vorkommen?

Dasselbe wie bei regulären Dictionaries – das spätere Element überschreibt das frühere. Dies hat den Nebeneffekt, dass die Position des ersten Schlüssels verwendet wird, da nur der Wert tatsächlich überschrieben wird.

>>> OrderedDict([('a', 1), ('b', 2), ('a', 3)])
collections.OrderedDict([('a', 3), ('b', 2)])

Dieses Verhalten entspricht bestehenden Implementierungen in Python, dem PHP-Array und der Hashmap in Ruby 1.9.

Ist das geordnete Dictionary eine Unterklasse von dict? Warum?

Ja. Wie defaultdict ist ein geordnetes Dictionary eine Unterklasse von dict. Eine Unterklasse von dict zu sein, macht einige Methoden schneller (wie __getitem__ und __len__). Noch wichtiger ist, dass geordnete Dictionaries aufgrund der Unterklasse von dict mit Werkzeugen wie json, die dict-Eingaben benötigen und isinstance(d, dict) testen, verwendet werden können.

Gibt es Einschränkungen durch das Unterklasse von dict?

Ja. Da die API für dicts in Py2.x und Py3.x unterschiedlich ist, muss auch die OrderedDict-API unterschiedlich sein. Daher muss die Py2.7-Version iterkeys, itervalues und iteritems überschreiben.

Gibt OrderedDict.popitem() ein bestimmtes Schlüssel/Wert-Paar zurück?

Ja. Es entfernt den zuletzt eingefügten neuen Schlüssel und seinen entsprechenden Wert. Dies entspricht dem üblichen LIFO-Verhalten, das bei traditionellen Push/Pop-Paaren auftritt. Es ist semantisch äquivalent zu k=list(od)[-1]; v=od[k]; del od[k]; return (k,v). Die tatsächliche Implementierung ist effizienter und entfernt direkt aus einer sortierten Liste von Schlüsseln.

Unterstützt OrderedDict Indizierung, Slicing und ähnliches?

Tatsächlich implementiert OrderedDict nicht die Sequence-Schnittstelle. Vielmehr ist es ein MutableMapping, das sich die Reihenfolge der Schlüsseleinfügung merkt. Die einzige sequenzähnliche Ergänzung ist die Unterstützung für reversed.

Ein weiterer Vorteil der Nichtzulassung von Indizierung ist, dass sie die Möglichkeit einer schnellen C-Implementierung mit verketteten Listen offen lässt.

Unterstützt OrderedDict alternative Sortierreihenfolgen wie alphabetisch?

Nein. Wer andere Sortierreihenfolgen wünscht, muss wirklich eine andere Technik anwenden. Das OrderedDict dient ausschließlich der Aufzeichnung der Einfügungsreihenfolge. Wenn eine andere Reihenfolge von Interesse ist, dann ist eine andere Struktur (wie eine In-Memory-Datenbank) wahrscheinlich besser geeignet.

Wie gut funktioniert OrderedDict mit dem json-Modul, PyYAML und ConfigParser?

Für json ist die gute Nachricht, dass der Encoder von json die Iterationsreihenfolge von OrderedDict respektiert

>>> items = [('one', 1), ('two', 2), ('three',3), ('four',4), ('five',5)]
>>> json.dumps(OrderedDict(items))
'{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'

In Py2.6 übergibt der object_hook für json-Decoder ein bereits erstelltes Dictionary, sodass die Reihenfolge verloren geht, bevor der object_hook es sieht. Dieses Problem wird für Python 2.7/3.1 behoben, indem ein neuer Hook hinzugefügt wird, der die Reihenfolge beibehält (siehe https://github.com/python/cpython/issues/49631 ). Mit dem neuen Hook kann die Reihenfolge erhalten bleiben.

>>> jtext = '{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'
>>> json.loads(jtext, object_pairs_hook=OrderedDict)
OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})

Für PyYAML ist eine vollständige Round-Trip-Funktion problemlos möglich.

>>> ytext = yaml.dump(OrderedDict(items))
>>> print ytext
!!python/object/apply:collections.OrderedDict
- - [one, 1]
  - [two, 2]
  - [three, 3]
  - [four, 4]
  - [five, 5]

>>> yaml.load(ytext)
OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})

Für das ConfigParser-Modul ist der Round-Trip ebenfalls problemlos möglich. Benutzerdefinierte Dictionaries wurden in Py2.6 speziell zur Unterstützung geordneter Dictionaries hinzugefügt.

>>> config = ConfigParser(dict_type=OrderedDict)
>>> config.read('myconfig.ini')
>>> config.remove_option('Log', 'error')
>>> config.write(open('myconfig.ini', 'w'))

Wie geht OrderedDict mit Gleichheitstests um?

Der Vergleich zweier geordneter Dictionaries impliziert, dass der Test ordnungsempfindlich ist, so dass list (od1.items())==list(od2.items()).

Wenn geordnete Dictionaries mit anderen Mappings verglichen werden, wird ihr ordnungsunabhängiger Vergleich verwendet. Dies ermöglicht es, geordnete Dictionaries überall dort einzusetzen, wo reguläre Dictionaries verwendet werden.

Wie wird das __repr__-Format die Reihenfolge während eines repr/eval-Round-Trips beibehalten?

OrderedDict([(‘a’, 1), (‘b’, 2)])

Welche Kompromisse gibt es bei den möglichen zugrunde liegenden Datenstrukturen?

• Die Beibehaltung einer sortierten Liste von Schlüsseln ist bei allen Operationen schnell, außer bei __delitem__(), das zu einer O(n)-Übung wird. Diese Datenstruktur führt zu sehr einfachem Code und wenig verschwendetem Speicherplatz.
• Die Beibehaltung eines separaten Dictionaries zur Aufzeichnung von Einfügungssequenznummern macht den Code etwas komplexer. Alle grundlegenden Operationen sind O(1), aber der konstante Faktor für __setitem__() und __delitem__() ist erhöht, was bedeutet, dass jeder Anwendungsfall für diese Beschleunigung bezahlen muss (da alle Aufbauten über __setitem__() laufen). Außerdem verursacht die erste Traversierung Kosten für eine einmalige Sortierung von O(n log n). Die Speicherkosten sind doppelt so hoch wie bei der Methode mit der sortierten Schlüssel liste.
• Eine in C geschriebene Version könnte eine verkettete Liste verwenden. Der Code wäre komplexer als bei den anderen beiden Ansätzen, würde aber Speicher sparen und die gleiche Big-Oh-Leistung wie reguläre Dictionaries beibehalten. Dies ist die schnellste und speichereffizienteste.

Referenzimplementierung

Eine Implementierung mit Tests und Dokumentation ist unter

OrderedDict Patch

Die vorgeschlagene Version hat mehrere Vorteile

• Strikte Einhaltung der MutableMapping-API und keine neuen Methoden, so dass die Lernkurve nahezu Null ist. Es ist einfach ein Dictionary, das sich die Einfügungsreihenfolge merkt.
• Generell gute Leistung. Die Big-Oh-Zeiten sind die gleichen wie bei regulären Dictionaries, mit Ausnahme der Schlüssellöschung, die O(n) ist.

Andere Implementierungen von geordneten Dictionaries in verschiedenen Python-Projekten oder eigenständigen Bibliotheken, die die hier vorgeschlagene API inspiriert haben, sind

• odict in Python
• odict in Babel
• OrderedDict in Django
• Das odict-Modul
• ordereddict (eine C-Implementierung des odict-Moduls)
• StableDict
• Armin Rigos OrderedDict

Zukünftige Richtungen

Mit der Verfügbarkeit eines geordneten Dictionaries in der Standardbibliothek können andere Bibliotheken davon profitieren. Zum Beispiel könnte ElementTree in Zukunft odicts zurückgeben, die die Attributreihenfolge der Quelldatei beibehalten.

Referenzen

Urheberrecht

Dieses Dokument wurde gemeinfrei erklärt.