Sortiertechniken¶
Python-Listen haben eine integrierte Methode list.sort(), die die Liste an ihrem Platz verändert. Es gibt außerdem die integrierte Funktion sorted(), die aus einem iterierbaren Objekt eine neue sortierte Liste baut.
In diesem Dokument betrachten wir die verschiedenen Techniken, mit denen sich Daten in Python sortieren lassen.
Grundlagen des Sortierens¶
Einfach aufsteigend zu sortieren ist sehr leicht: Rufe einfach die Funktion sorted() auf. Sie gibt eine neue sortierte Liste zurück:
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]
Du kannst auch die Methode list.sort() verwenden. Sie verändert die Liste an ihrem Platz (und gibt None zurück, um Verwirrung zu vermeiden). Üblicherweise ist sie weniger bequem als sorted() – wenn du die ursprüngliche Liste aber nicht mehr brauchst, ist sie etwas effizienter.
>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
Ein weiterer Unterschied ist, dass die Methode list.sort() nur für Listen definiert ist. Die Funktion sorted() nimmt dagegen jedes iterierbare Objekt an.
>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]
Schlüsselfunktionen¶
Die Methode list.sort() und die Funktionen sorted(), min(), max(), heapq.nsmallest() und heapq.nlargest() haben einen Parameter key, mit dem sich eine Funktion (oder ein anderes aufrufbares Objekt) angeben lässt, die vor den Vergleichen auf jedes Listenelement angewendet wird.
Hier zum Beispiel ein Zeichenkettenvergleich ohne Beachtung der Groß- und Kleinschreibung mit str.casefold():
>>> sorted("This is a test string from Andrew".split(), key=str.casefold)
['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
Der Wert des Parameters key sollte eine Funktion (oder ein anderes aufrufbares Objekt) sein, die ein einzelnes Argument nimmt und einen Schlüssel für die Zwecke des Sortierens zurückgibt. Diese Technik ist schnell, weil die Schlüsselfunktion für jeden Eingabedatensatz genau einmal aufgerufen wird.
Ein häufiges Muster ist, zusammengesetzte Objekte anhand einiger ihrer Indizes als Schlüssel zu sortieren. Zum Beispiel:
>>> student_tuples = [
... ('john', 'A', 15),
... ('jane', 'B', 12),
... ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2]) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Dieselbe Technik funktioniert für Objekte mit benannten Attributen. Zum Beispiel:
>>> class Student:
... def __init__(self, name, grade, age):
... self.name = name
... self.grade = grade
... self.age = age
... def __repr__(self):
... return repr((self.name, self.grade, self.age))
>>> student_objects = [
... Student('john', 'A', 15),
... Student('jane', 'B', 12),
... Student('dave', 'B', 10),
... ]
>>> sorted(student_objects, key=lambda student: student.age) # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Objekte mit benannten Attributen lassen sich mit einer gewöhnlichen Klasse erzeugen, wie oben gezeigt, oder sie können Instanzen einer dataclass oder eines benannten Tupels sein.
Funktionen des operator-Moduls und teilweise Funktionsauswertung¶
Die oben gezeigten Muster für Schlüsselfunktionen sind sehr verbreitet, daher bietet Python Hilfsfunktionen, die Zugriffsfunktionen einfacher und schneller machen. Das Modul operator enthält itemgetter(), attrgetter() und eine Funktion methodcaller().
Mit diesen Funktionen werden die obigen Beispiele einfacher und schneller:
>>> from operator import itemgetter, attrgetter
>>> sorted(student_tuples, key=itemgetter(2))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
>>> sorted(student_objects, key=attrgetter('age'))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Die Funktionen des operator-Moduls erlauben mehrere Sortierebenen. Um zum Beispiel nach grade und dann nach age zu sortieren:
>>> sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
>>> sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
Das Modul functools bietet ein weiteres hilfreiches Werkzeug, um Schlüsselfunktionen zu bauen. Die Funktion partial() kann die Stelligkeit einer Funktion mit mehreren Argumenten verringern und sie damit als Schlüsselfunktion verwendbar machen.
>>> from functools import partial
>>> from unicodedata import normalize
>>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()
>>> sorted(names, key=partial(normalize, 'NFD'))
['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']
>>> sorted(names, key=partial(normalize, 'NFC'))
['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']
Aufsteigend und absteigend¶
Sowohl list.sort() als auch sorted() nehmen einen Parameter reverse mit einem booleschen Wert an. Damit wird absteigendes Sortieren gekennzeichnet. Um zum Beispiel die Studentendaten in umgekehrter age-Reihenfolge zu bekommen:
>>> sorted(student_tuples, key=itemgetter(2), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
>>> sorted(student_objects, key=attrgetter('age'), reverse=True)
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
Sortierstabilität und zusammengesetzte Sortierungen¶
Sortierungen sind garantiert stabil. Das heißt, dass die ursprüngliche Reihenfolge erhalten bleibt, wenn mehrere Datensätze denselben Schlüssel haben.
>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
Beachte, wie die beiden Datensätze für blue ihre ursprüngliche Reihenfolge behalten, sodass ('blue', 1) garantiert vor ('blue', 2) steht.
Diese wunderbare Eigenschaft erlaubt es dir, zusammengesetzte Sortierungen in einer Folge von Sortierschritten aufzubauen. Um zum Beispiel die Studentendaten nach absteigendem grade und dann nach aufsteigendem age zu sortieren, sortiere zuerst nach age und dann erneut nach grade:
>>> s = sorted(student_objects, key=attrgetter('age')) # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True) # now sort on primary key, descending
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Das lässt sich in eine Hüllfunktion abstrahieren, die eine Liste und Tupel aus Feld und Richtung annimmt, um in mehreren Durchgängen danach zu sortieren.
>>> def multisort(xs, specs):
... for key, reverse in reversed(specs):
... xs.sort(key=attrgetter(key), reverse=reverse)
... return xs
>>> multisort(list(student_objects), (('grade', True), ('age', False)))
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Der in Python verwendete Algorithmus Timsort führt mehrere Sortierungen effizient aus, weil er jede in einem Datensatz bereits vorhandene Ordnung ausnutzen kann.
Decorate-Sort-Undecorate¶
Dieses Idiom heißt nach seinen drei Schritten Decorate-Sort-Undecorate:
Zuerst wird die Ausgangsliste mit neuen Werten dekoriert, die die Sortierreihenfolge bestimmen.
Danach wird die dekorierte Liste sortiert.
Zuletzt werden die Dekorationen entfernt. So entsteht eine Liste, die nur die Ausgangswerte in der neuen Reihenfolge enthält.
Um zum Beispiel die Studentendaten mit dem DSU-Ansatz nach grade zu sortieren:
>>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
>>> decorated.sort()
>>> [student for grade, i, student in decorated] # undecorate
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
Dieses Idiom funktioniert, weil Tupel lexikografisch verglichen werden: Zuerst werden die ersten Elemente verglichen. Sind sie gleich, werden die zweiten Elemente verglichen, und so weiter.
Es ist nicht in allen Fällen zwingend nötig, den Index i in die dekorierte Liste aufzunehmen, aber es bringt zwei Vorteile:
Die Sortierung ist stabil – haben zwei Elemente denselben Schlüssel, bleibt ihre Reihenfolge in der sortierten Liste erhalten.
Die ursprünglichen Elemente müssen nicht vergleichbar sein, weil die Reihenfolge der dekorierten Tupel von höchstens den ersten zwei Elementen bestimmt wird. So könnte die ursprüngliche Liste zum Beispiel komplexe Zahlen enthalten, die sich nicht direkt sortieren lassen.
Ein anderer Name für dieses Idiom ist Schwartzian transform, nach Randal L. Schwartz, der es unter Perl-Programmierern bekannt gemacht hat.
Da Python beim Sortieren inzwischen Schlüsselfunktionen bietet, braucht man diese Technik nicht mehr oft.
Vergleichsfunktionen¶
Anders als Schlüsselfunktionen, die zum Sortieren einen absoluten Wert zurückgeben, berechnet eine Vergleichsfunktion die relative Ordnung zweier Eingaben.
Eine Balkenwaage vergleicht zum Beispiel zwei Proben und liefert eine relative Ordnung: leichter, gleich oder schwerer. Ebenso gibt eine Vergleichsfunktion wie cmp(a, b) einen negativen Wert für „kleiner als“, null bei gleichen Eingaben oder einen positiven Wert für „größer als“ zurück.
Vergleichsfunktionen trifft man häufig, wenn man Algorithmen aus anderen Sprachen überträgt. Außerdem bieten manche Bibliotheken Vergleichsfunktionen als Teil ihrer API an. locale.strcoll() ist zum Beispiel eine Vergleichsfunktion.
Für diese Fälle bietet Python functools.cmp_to_key, um die Vergleichsfunktion so zu umhüllen, dass sie als Schlüsselfunktion verwendbar wird:
sorted(words, key=cmp_to_key(strcoll)) # locale-aware sort order
Strategien für nicht ordenbare Typen und Werte¶
Beim Sortieren kann es zu einer Reihe von Typ- und Wertproblemen kommen. Hier einige Strategien, die helfen können:
Wandle nicht vergleichbare Eingabetypen vor dem Sortieren in Zeichenketten um:
>>> data = ['twelve', '11', 10]
>>> sorted(map(str, data))
['10', '11', 'twelve']
Das ist nötig, weil die meisten Vergleiche über Typgrenzen hinweg einen TypeError auslösen.
Entferne besondere Werte vor dem Sortieren:
>>> from math import isnan
>>> from itertools import filterfalse
>>> data = [3.3, float('nan'), 1.1, 2.2]
>>> sorted(filterfalse(isnan, data))
[1.1, 2.2, 3.3]
Das ist nötig, weil der IEEE-754-Standard festlegt: „Every NaN shall compare unordered with everything, including itself.“
Ebenso lässt sich None aus Datensätzen entfernen:
>>> data = [3.3, None, 1.1, 2.2]
>>> sorted(x for x in data if x is not None)
[1.1, 2.2, 3.3]
Das ist nötig, weil None nicht mit anderen Typen vergleichbar ist.
Wandle Abbildungstypen vor dem Sortieren in sortierte Elementlisten um:
>>> data = [{'a': 1}, {'b': 2}]
>>> sorted(data, key=lambda d: sorted(d.items()))
[{'a': 1}, {'b': 2}]
Das ist nötig, weil Vergleiche zwischen Dicts einen TypeError auslösen.
Wandle Mengentypen vor dem Sortieren in sortierte Listen um:
>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
>>> sorted(map(sorted, data))
[['a', 'b', 'c'], ['b', 'c', 'd']]
Das ist nötig, weil die in Mengentypen enthaltenen Elemente keine festgelegte Reihenfolge haben. So kann list({'a', 'b'}) zum Beispiel entweder ['a', 'b'] oder ['b', 'a'] ergeben.
Verschiedenes¶
Für ein Sortieren, das das Gebietsschema beachtet, verwende
locale.strxfrm()als Schlüsselfunktion oderlocale.strcoll()als Vergleichsfunktion. Das ist nötig, weil „alphabetische“ Sortierreihenfolgen sich zwischen Kulturen unterscheiden können, selbst wenn das zugrunde liegende Alphabet dasselbe ist.Der Parameter reverse erhält die Sortierstabilität (sodass Datensätze mit gleichen Schlüsseln ihre ursprüngliche Reihenfolge behalten). Interessanterweise lässt sich dieser Effekt auch ohne den Parameter nachbilden, indem man die integrierte Funktion
reversed()zweimal verwendet:>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)] >>> standard_way = sorted(data, key=itemgetter(0), reverse=True) >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0)))) >>> assert standard_way == double_reversed >>> standard_way [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]
Die Sortierroutinen verwenden beim Vergleich zweier Objekte
<. Eine Standard-Sortierreihenfolge lässt sich einer Klasse daher leicht hinzufügen, indem man eine Methode__lt__()definiert:>>> Student.__lt__ = lambda self, other: self.age < other.age >>> sorted(student_objects) [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
Beachte aber, dass
<auf__gt__()zurückfallen kann, wenn__lt__()nicht implementiert ist (Einzelheiten zur Mechanik stehen beiobject.__lt__()). Um Überraschungen zu vermeiden, empfiehlt PEP 8, alle sechs Vergleichsmethoden zu implementieren. Der Dekorator@~functools.total_orderingist dafür da, diese Aufgabe zu erleichtern.Schlüsselfunktionen müssen nicht unmittelbar von den sortierten Objekten abhängen. Eine Schlüsselfunktion kann auch auf äußere Quellen zugreifen. Sind die Noten der Studenten zum Beispiel in einem Wörterbuch gespeichert, lassen sie sich verwenden, um eine separate Liste von Studentennamen zu sortieren:
>>> students = ['dave', 'john', 'jane'] >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'} >>> sorted(students, key=newgrades.__getitem__) ['jane', 'dave', 'john']
Teilweises Sortieren¶
Manche Anwendungen brauchen nur einen Teil der Daten geordnet. Die Standardbibliothek bietet mehrere Werkzeuge, die weniger Arbeit leisten als eine vollständige Sortierung:
min()undmax()geben den kleinsten beziehungsweise den größten Wert zurück. Diese Funktionen gehen die Eingabedaten in einem einzigen Durchgang durch und brauchen so gut wie keinen Hilfsspeicher.heapq.nsmallest()undheapq.nlargest()geben die n kleinsten beziehungsweise die n größten Werte zurück. Diese Funktionen gehen die Daten in einem einzigen Durchgang durch und halten dabei immer nur n Elemente im Speicher. Für Werte von n, die im Verhältnis zur Anzahl der Eingaben klein sind, führen diese Funktionen weit weniger Vergleiche durch als eine vollständige Sortierung.heapq.heappush()undheapq.heappop()erzeugen und pflegen eine teilweise sortierte Anordnung der Daten, die das kleinste Element an Position0hält. Diese Funktionen eignen sich dafür, Prioritätswarteschlangen umzusetzen, wie sie häufig für die Ablaufplanung von Aufgaben verwendet werden.