Zusammenfassung

Diese PEP schlägt eine „Nach Wert sortieren“-Operation für Dictionaries vor. Der Hauptvorteil liegt in der „Batterien inklusive“-Unterstützung für ein gängiges Python-Idiom, das in seiner aktuellen Form sowohl für Anfänger schwer zu verstehen als auch für alle umständlich zu implementieren ist.

BDFL-Verkündigung

Diese PEP wurde abgelehnt, da der Bedarf weitgehend durch die integrierte Funktion sorted() von Py2.4 erfüllt wurde

>>> sorted(d.iteritems(), key=itemgetter(1), reverse=True)
[('b', 23), ('d', 17), ('c', 5), ('a', 2), ('e', 1)]

oder nur für die Schlüssel

sorted(d, key=d.__getitem__, reverse=True)
['b', 'd', 'c', 'a', 'e']

Auch die Funktion heapq.nlargest() von Python 2.5 adressiert den gängigen Anwendungsfall, nur einige der Elemente mit den höchsten Werten zu finden.

>>> nlargest(2, d.iteritems(), itemgetter(1))
[('b', 23), ('d', 17)]

Motivation

Eine häufige Verwendung von Dictionaries ist das Zählen von Vorkommen, indem der Wert von d[key] bei seinem ersten Auftreten auf 1 gesetzt und der Wert bei jedem nachfolgenden Auftreten inkrementiert wird. Dies kann auf verschiedene Arten geschehen, aber die get()-Methode ist am kürzesten.

d[key] = d.get(key, 0) + 1

Nachdem alle Vorkommen gezählt wurden, ist eine gängige Verwendung des resultierenden Dictionaries, die Vorkommen in sortierter Reihenfolge auszugeben, oft mit dem größten Wert zuerst.

Dies führt zu der Notwendigkeit, die Elemente eines Dictionaries nach Wert zu sortieren. Die kanonische Methode hierfür in Python ist, zuerst d.items() zu verwenden, um eine Liste der Dictionary-Elemente zu erhalten, dann die Reihenfolge jedes Element-Tupels von (Schlüssel, Wert) in (Wert, Schlüssel) zu invertieren, und dann die Liste zu sortieren; da Python die Liste basierend auf dem ersten Element des Tupels sortiert, wird die Liste der (invertierten) Elemente daher nach Wert sortiert. Falls gewünscht, kann die Liste dann umgekehrt und die Tupel können wieder zurück in (Schlüssel, Wert) invertiert werden. (Meiner Erfahrung nach ist die invertierte Tupelreihenfolge für die meisten Zwecke jedoch in Ordnung, z. B. für die Ausgabe der Liste.)

Zum Beispiel, gegeben eine Zählung von Vorkommen

>>> d = {'a':2, 'b':23, 'c':5, 'd':17, 'e':1}

könnten wir tun

>>> items = [(v, k) for k, v in d.items()]
>>> items.sort()
>>> items.reverse()             # so largest is first
>>> items = [(k, v) for v, k in items]

was zu

>>> items
[('b', 23), ('d', 17), ('c', 5), ('a', 2), ('e', 1)]

führt, was die Liste in nach Wert sortierter Reihenfolge zeigt, mit dem größten zuerst. (In diesem Fall wurde festgestellt, dass 'b' die meisten Vorkommen hatte.)

Dies funktioniert gut, ist aber in zweierlei Hinsicht „schwer zu verwenden“. Erstens ist dieses Idiom, obwohl erfahrenen Pythoneers bekannt, für Neulinge überhaupt nicht offensichtlich – weder in Bezug auf den Algorithmus (Invertieren der Reihenfolge von Element-Tupeln) noch auf die Implementierung (Verwendung von Listen-Komprensionen – einer fortgeschrittenen Python-Funktion). Zweitens erfordert es wiederholtes Tippen von viel „Kram“, was zu Langeweile und Fehlern führt.

Wir möchten daher lieber, dass Python eine Methode zum Sortieren von Dictionaries nach Wert bereitstellt, die sowohl für Neulinge leicht verständlich ist (oder, besser noch, *nicht* verstanden werden muss) als auch für alle einfacher zu verwenden ist.

Begründung

Wie Tim Peters angemerkt hat, bringt eine solche Sache das Problem mit sich, allen alles sein zu wollen. Daher werden wir den Umfang einschränken, um den „Sweet Spot“ zu treffen. Ungewöhnliche Fälle (z. B. Sortieren mit einer benutzerdefinierten Vergleichsfunktion) können natürlich „manuell“ mit den vorhandenen Methoden behandelt werden.

Hier sind einige einfache Möglichkeiten

Die items()-Methode von Dictionaries kann mit neuen Parametern mit Standardwerten erweitert werden, die volle Abwärtskompatibilität bieten

(1) items(sort_by_values=0, reversed=0)

oder vielleicht nur

(2) items(sort_by_values=0)

da das Umkehren einer Liste einfach genug ist.

Alternativ könnte items() uns einfach die (Schlüssel, Wert)-Reihenfolge kontrollieren lassen

(3) items(values_first=0)

Auch dies ist voll abwärtskompatibel. Es leistet weniger Arbeit als die anderen, aber es erleichtert zumindest den kompliziertesten/kniffligsten Teil des Sortierproblems nach Wert: das Invertieren der Reihenfolge von Element-Tupeln. Die Verwendung ist sehr einfach

items = d.items(1)
items.sort()
items.reverse()         # (if desired)

Der Hauptnachteil der drei vorherigen Ansätze ist der zusätzliche Overhead für den parameterlosen items()-Fall aufgrund der Notwendigkeit, Standardparameter zu verarbeiten. (Wenn man jedoch davon ausgeht, dass items() hauptsächlich zum Erstellen von Listen zum Sortieren nach Wert verwendet wird, ist dies praktisch kein Nachteil.)

Alternativ könnten wir eine neue Dictionary-Methode hinzufügen, die irgendwie „Sortieren“ verkörpert. Dieser Ansatz bietet zwei Vorteile. Erstens vermeidet er zusätzlichen Overhead für die items()-Methode. Zweitens ist er vielleicht zugänglicher für Neulinge: Wenn sie nach einer Methode zum Sortieren von Dictionaries suchen, stoßen sie hoffentlich auf diese und müssen die Feinheiten der Tupelinvertierung und Listensortierung nicht verstehen, um nach Wert zu sortieren.

Um die vier grundlegenden Möglichkeiten des Sortierens nach Schlüssel/Wert und in Vorwärts-/Rückwärtsrichtung zu ermöglichen, könnten wir diese Methode hinzufügen

(4) sorted_items(by_value=0, reversed=0)

Ich glaube, der häufigste Fall wäre tatsächlich by_value=1, reversed=1, aber die hier angegebenen Standardwerte könnten zu weniger Überraschungen bei den Benutzern führen: sorted_items() wäre dasselbe wie items() gefolgt von sort().

Schließlich (als letztes Mittel) könnten wir verwenden

(5) items_sorted_by_value(reversed=0)

Implementierung

Die vorgeschlagenen Dictionary-Methoden müssten in C implementiert werden. Vermutlich wäre die Implementierung recht einfach, da sie nur einige Aufrufe der vorhandenen Python-Mechanismen beinhaltet.

Bedenken

Abgesehen vom Laufzeit-Overhead, der bereits in den Möglichkeiten 1 bis 3 behandelt wurde, fallen Bedenken bei diesem Vorschlag wahrscheinlich in die Kategorien „Feature-Aufblähung“ und/oder „Code-Aufblähung“. Ich glaube jedoch, dass mehrere der hier vorgeschlagenen Ideen zu einer ziemlich minimalen Aufblähung führen werden, was einen guten Kompromiss zwischen Aufblähung und „Mehrwert“ ergibt.

Tim Peters hat angemerkt, dass die Implementierung in C möglicherweise nicht wesentlich schneller ist als die heutige Implementierung in Python. Die Hauptvorteile, die hier angestrebt werden, sind jedoch „Zugänglichkeit“ und „Benutzerfreundlichkeit“, nicht „Geschwindigkeit“. Solange es also nicht merklich langsamer ist (im Fall von reinem items() muss die Geschwindigkeit keine Rolle spielen).

Referenzen

Ein verwandter Thread namens „counting occurrences“ erschien im August 2001 auf comp.lang.python. Dies enthielt Beispiele für Ansätze zur Systematisierung des Sortierproblems nach Wert durch dessen Implementierung als wiederverwendbare Python-Funktionen und -Klassen.

Urheberrecht

Dieses Dokument wurde gemeinfrei erklärt.