Sortiertechniken

Autor:

Andrew Dalke und Raymond Hettinger

Python-Listen haben eine eingebaute Methode list.sort(), die die Liste direkt modifiziert. Es gibt auch eine eingebaute Funktion sorted(), die aus einem Iterable eine neue sortierte Liste erstellt.

In diesem Dokument werden die verschiedenen Techniken zum Sortieren von Daten mit Python untersucht.

Grundlagen des Sortierens

Eine einfache aufsteigende Sortierung ist sehr einfach: rufen Sie einfach die Funktion sorted() auf. Sie gibt eine neue sortierte Liste zurück.

>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

Sie können auch die Methode list.sort() verwenden. Sie modifiziert die Liste direkt (und gibt None zurück, um Verwirrung zu vermeiden). Normalerweise ist sie weniger praktisch als sorted() – aber wenn Sie die ursprüngliche Liste nicht benötigen, ist sie geringfügig effizienter.

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

Ein weiterer Unterschied besteht darin, dass die Methode list.sort() nur für Listen definiert ist. Im Gegensatz dazu akzeptiert die Funktion sorted() jedes Iterable.

>>> 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() verfügen über einen Parameter key, um eine Funktion (oder einen anderen aufrufbaren Wert) anzugeben, die auf jedes Listenelement angewendet wird, bevor Vergleiche durchgeführt werden.

Hier ist zum Beispiel ein beispielhafter Vergleich von Zeichenketten, der die Groß- und Kleinschreibung ignoriert, unter Verwendung von 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 anderer aufrufbarer Wert) sein, die ein einzelnes Argument entgegennimmt und einen Schlüssel für Sortierzwecke zurückgibt. Diese Technik ist schnell, da die Schlüsselfunktion genau einmal für jeden Eingaberecord aufgerufen wird.

Ein gängiges Muster ist das Sortieren komplexer Objekte anhand einiger Indizes des Objekts als Schlüssel. 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)]

Die gleiche Technik funktioniert auch 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 können durch eine normale Klasse wie oben gezeigt erstellt werden, oder sie können Instanzen von dataclass oder ein benanntes Tupel sein.

Operator-Modul-Funktionen und partielle Funktionsauswertung

Die oben gezeigten Muster für Schlüsselfunktionen sind sehr verbreitet, daher bietet Python Hilfsfunktionen, um Zugriffsparameter einfacher und schneller zu gestalten. Das Modul operator enthält itemgetter(), attrgetter() und die 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 ermöglichen mehrstufige Sortierungen. Um beispielsweise nach Note und dann nach Alter 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 nützliches Werkzeug zur Erstellung von Schlüsselfunktionen. Die Funktion partial() kann die Stelligkeit einer Funktion mit mehreren Argumenten reduzieren und sie so für die Verwendung als Schlüsselfunktion geeignet 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() akzeptieren einen Parameter reverse mit einem booleschen Wert. Dieser wird verwendet, um absteigende Sortierungen zu kennzeichnen. Um beispielsweise die Studentendaten in umgekehrter Altersreihenfolge zu erhalten

>>> 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 komplexe Sortierungen

Sortierungen sind garantiert stabil. Das bedeutet, dass bei mehreren Datensätzen mit demselben Schlüssel ihre ursprüngliche Reihenfolge beibehalten wird.

>>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
>>> sorted(data, key=itemgetter(0))
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

Beachten Sie, wie die beiden Datensätze für blau ihre ursprüngliche Reihenfolge beibehalten, sodass garantiert ist, dass ('blau', 1) vor ('blau', 2) steht.

Diese wunderbare Eigenschaft ermöglicht es Ihnen, komplexe Sortierungen in einer Reihe von Sortierschritten aufzubauen. Um beispielsweise die Studentendaten nach absteigender Note und dann nach aufsteigendem Alter zu sortieren, führen Sie zuerst die Alterssortierung durch und sortieren dann erneut nach Note.

>>> 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)]

Dies kann in eine Wrapper-Funktion abstrahiert werden, die eine Liste und Tupel von Feldern und Reihenfolgen entgegennehmen kann, um sie in mehreren Durchläufen 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 Timsort-Algorithmus führt mehrere Sortierungen effizient durch, da er jede bereits vorhandene Ordnung in einem Datensatz nutzen kann.

Dekorieren-Sortieren-Entdekorieren

Dieses Idiom wird nach seinen drei Schritten Decorate-Sort-Undecorate genannt.

• Zuerst wird die ursprüngliche Liste mit neuen Werten dekoriert, die die Sortierreihenfolge steuern.

• Zweitens wird die dekorierte Liste sortiert.

• Schließlich werden die Dekorationen entfernt, wodurch eine Liste erstellt wird, die nur die ursprünglichen Werte in der neuen Reihenfolge enthält.

Um beispielsweise die Studentendaten nach Note mit dem DSU-Ansatz 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, da Tupel lexikographisch verglichen werden; die ersten Elemente werden verglichen; wenn sie gleich sind, werden die zweiten Elemente verglichen und so weiter.

Es ist nicht in allen Fällen unbedingt erforderlich, den Index i in die dekorierte Liste aufzunehmen, aber die Aufnahme hat zwei Vorteile:

• Die Sortierung ist stabil – wenn zwei Elemente denselben Schlüssel haben, wird ihre Reihenfolge in der sortierten Liste beibehalten.

• Die ursprünglichen Elemente müssen nicht vergleichbar sein, da die Reihenfolge der dekorierten Tupel höchstens durch die ersten beiden Elemente bestimmt wird. So könnte zum Beispiel die ursprüngliche Liste komplexe Zahlen enthalten, die nicht direkt sortiert werden können.

Ein anderer Name für dieses Idiom ist Schwartzian transform, nach Randal L. Schwartz, der es unter Perl-Programmierern populär gemacht hat.

Da Python-Sortierungen jetzt Schlüsselfunktionen bieten, wird diese Technik nicht mehr oft benötigt.

Vergleichsfunktionen

Im Gegensatz zu Schlüsselfunktionen, die einen absoluten Wert für die Sortierung zurückgeben, berechnet eine Vergleichsfunktion die relative Ordnung für zwei Eingaben.

Zum Beispiel vergleicht eine Balkenwaage zwei Proben und gibt eine relative Ordnung zurück: leichter, gleich oder schwerer. Ebenso gibt eine Vergleichsfunktion wie cmp(a, b) einen negativen Wert für kleiner als, Null, wenn die Eingaben gleich sind, oder einen positiven Wert für größer als zurück.

Es ist üblich, Vergleichsfunktionen beim Übersetzen von Algorithmen aus anderen Sprachen anzutreffen. Einige Bibliotheken stellen auch Vergleichsfunktionen als Teil ihrer API bereit. Zum Beispiel ist locale.strcoll() eine Vergleichsfunktion.

Um diesen Situationen Rechnung zu tragen, stellt Python functools.cmp_to_key zur Verfügung, um die Vergleichsfunktion zu wrappen und sie als Schlüsselfunktion verwendbar zu machen.

sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order

Strategien für unsortierbare Typen und Werte

Beim Sortieren können verschiedene Typ- und Wertprobleme auftreten. Hier sind einige Strategien, die helfen können:

• Konvertieren Sie nicht vergleichbare Eingabetypen vor der Sortierung in Zeichenketten.

>>> data = ['twelve', '11', 10]
>>> sorted(map(str, data))
['10', '11', 'twelve']

Dies ist erforderlich, da die meisten vergleiche zwischen verschiedenen Typen einen TypeError auslösen.

• Entfernen Sie spezielle Werte vor der Sortierung.

>>> 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]

Dies ist erforderlich, da der IEEE-754-Standard besagt: „Jedes NaN vergleicht sich ungeordnet mit allem, einschließlich sich selbst.“

Ebenso kann None aus Datensätzen entfernt werden.

>>> 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]

Dies ist erforderlich, da None nicht mit anderen Typen vergleichbar ist.

• Konvertieren Sie Mapping-Typen vor der Sortierung in sortierte Elementlisten.

>>> data = [{'a': 1}, {'b': 2}]
>>> sorted(data, key=lambda d: sorted(d.items()))
[{'a': 1}, {'b': 2}]

Dies ist erforderlich, da Dict-zu-Dict-Vergleiche einen TypeError auslösen.

• Konvertieren Sie Set-Typen vor der Sortierung in sortierte Listen.

>>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
>>> sorted(map(sorted, data))
[['a', 'b', 'c'], ['b', 'c', 'd']]

Dies ist erforderlich, da die Elemente, die in Set-Typen enthalten sind, keine deterministische Reihenfolge haben. Zum Beispiel kann list({'a', 'b'}) entweder ['a', 'b'] oder ['b', 'a'] ergeben.

Sonstiges

• Für lokalisierte Sortierungen verwenden Sie locale.strxfrm() für eine Schlüsselfunktion oder locale.strcoll() für eine Vergleichsfunktion. Dies ist notwendig, da „alphabetische“ Sortierreihenfolgen je nach Kultur variieren können, selbst wenn das zugrunde liegende Alphabet dasselbe ist.

• Der Parameter reverse behält die Sortierstabilität bei (sodass Datensätze mit gleichen Schlüsseln die ursprüngliche Reihenfolge beibehalten). Interessanterweise kann dieser Effekt ohne den Parameter simuliert werden, indem die eingebaute Funktion reversed() zweimal verwendet wird.

  >>> 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 <, wenn sie zwei Objekte vergleichen. Daher ist es einfach, einer Klasse eine Standard-Sortierreihenfolge hinzuzufügen, indem eine Methode __lt__() definiert wird.

  >>> Student.__lt__ = lambda self, other: self.age < other.age
  >>> sorted(student_objects)
  [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
  

  Beachten Sie jedoch, dass < auf __gt__() zurückfallen kann, wenn __lt__() nicht implementiert ist (siehe object.__lt__() für Details zu den Mechanismen). Um Überraschungen zu vermeiden, empfiehlt PEP 8 die Implementierung aller sechs Vergleichsmethoden. Der Dekorator total_ordering() erleichtert diese Aufgabe.

• Schlüsselfunktionen müssen nicht direkt von den zu sortierenden Objekten abhängen. Eine Schlüsselfunktion kann auch auf externe Ressourcen zugreifen. Wenn beispielsweise die Noten der Studenten in einem Wörterbuch gespeichert sind, können diese verwendet werden, 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']
  

Teilweise Sortierungen

Einige Anwendungen benötigen nur die Sortierung eines Teils der Daten. Die Standardbibliothek bietet mehrere Werkzeuge, die weniger Arbeit leisten als eine vollständige Sortierung.

• min() und max() geben den kleinsten bzw. größten Wert zurück. Diese Funktionen durchlaufen die Eingabedaten einmal und benötigen fast keinen zusätzlichen Speicher.

• heapq.nsmallest() und heapq.nlargest() geben die n kleinsten bzw. größten Werte zurück. Diese Funktionen durchlaufen die Daten einmal und behalten jeweils nur n Elemente im Speicher. Für Werte von n, die klein im Verhältnis zur Anzahl der Eingaben sind, führen diese Funktionen weit weniger Vergleiche durch als eine vollständige Sortierung.

• heapq.heappush() und heapq.heappop() erstellen und pflegen eine teilweise sortierte Anordnung von Daten, die das kleinste Element an Position 0 hält. Diese Funktionen eignen sich zur Implementierung von Prioritätswarteschlangen, die häufig für die Aufgabenplanung verwendet werden.