Sortierungs-Tutorium

Tutorium: Sortierung und das Decorate/Sort/Undecorate-Pattern

Dieses kurze Tutorium führt anhand einer interaktiven Python-Interpretersitzung in die Benutzung der sort-Methode und der verwandten, eingebauten Funktion sorted ein.

Einfache Listen sortieren

Wir importieren benötigte Module und erzeugen uns eine ungeordnete Liste:

>>> import random
>>> l = range(1,10)
>>> l
[1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> random.shuffle(l)
>>> l
[7, 3, 9, 2, 5, 8, 1, 6, 4]

Die Standardsortierungsmethode sort verändert die Liste als Nebeneffekt:

>>> l.sort()
>>> l
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Die Sortierungsreihenfolge richtet sich nach dem Typ der Objekte in der Liste. Numerische Typen (Int, Float, Complex) werden numerisch sortiert, Strings und Unicode alphabetisch, für alle anderen Objekte ist die Sortierungsreihenfolge unbestimmt bzw. implementierungsabhängig [1].

[1]

Es sei denn sie implementieren eine __cmp__-Methode. Siehe die Python Sprachreferenz

Die Funktion sorted gibt die sortierte Liste zurück. sorted gibt es allerdings erst seit Python 2.4:

>>> random.shuffle(l)
>>> l1 = sorted(l)
>>> l
[5, 1, 7, 4, 9, 3, 6, 2, 8]

>>> l1
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Lass uns schauen, was noch möglich ist:

>>> help(list.sort)
Help on built-in function sort:

sort(...)
    L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
    cmp(x, y) -> -1, 0, 1

>>> help(sorted)
Help on built-in function sorted in module __builtin__:

sorted(...)
    sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list

Mehr Informationen gibt's in der Referenz der Python-Standardbibliothek.

Listen von komplexen Objekten sortieren

Was ist, wenn die einzelnen Elemente der zu sortierenden Liste, komplexere Objekte sind, z.B. Tupel mit mehreren Elementen?

>>> l2 = zip(l, l1)
>>> l2
[(5, 1), (1, 2), (7, 3), (4, 4), (9, 5), (3, 6), (6, 7), (2, 8), (8, 9)]

>>> sorted(l2)
[(1, 2), (2, 8), (3, 6), (4, 4), (5, 1), (6, 7), (7, 3), (8, 9), (9, 5)]

Aha, die Standardmethode scheint auch hier zu funktionieren, solange wir nach dem jeweils ersten Element der Tupel sortieren wollen. Aber was ist, wenn wir nach i[1] sortieren wollen? Oder eine Liste von Objekten nach einem bestimmten Attribut des Objekts?

Als Beispiel habe ich eine simple Klasse geschreiben, die eine Koordinate im dreidimensionalen Raum repräsentiert. Das Modul, in dem die Klasse und ein paar Hilfsfunktionen definiert sind, kann hier heruntergeladen werden.

Wir bauen uns nun eine Liste mit Objekten mit zufälligen x/y/z-Koordinaten zwischen 0 und 9:

>>> from sortdemo import ThreeDPoint,compare_point1, compare_point2
>>> pl = [ThreeDPoint(*random.sample(range(10), 3)) for i in range(10)]
>>> pl
[Point(x=7, y=5, z=6),
 Point(x=1, y=9, z=5),
 Point(x=7, y=9, z=4),
 Point(x=0, y=4, z=9),
 Point(x=7, y=2, z=5),
 Point(x=8, y=1, z=2),
 Point(x=0, y=6, z=2),
 Point(x=9, y=3, z=2),
 Point(x=2, y=3, z=5),
 Point(x=3, y=7, z=1)]

Lass uns versuchen diese Liste zu sortieren:

>>> sorted(pl)
[Point(x=7, y=5, z=6),
 Point(x=1, y=9, z=5),
 Point(x=7, y=9, z=4),
 Point(x=0, y=4, z=9),
 Point(x=7, y=2, z=5),
 Point(x=8, y=1, z=2),
 Point(x=0, y=6, z=2),
 Point(x=9, y=3, z=2),
 Point(x=2, y=3, z=5),
 Point(x=3, y=7, z=1)]

Hmm, das funktioniert wohl so nicht. Nun kommt das cmp-Argument von sort bzw . sorted ins Spiel. Es erwartet eine Funktion, die zwei Objekte miteinander vergleicht und -1, 0 oder 1 zurück gibt. Eine solche Funktion ist im Beispielmodul unter dem Namen compare_point1 definiert. Sie vergleicht das x-Attribut der zwei übergebenen (ThreeDPoint-)Objekte:

def compare_point1(p1, p2):
    if p1.x < p2.x:
        return -1
    elif p1.x > p2.x:
        return 1
    else:
        return 0

Und so wird die Funktion angewendet:

>>> sorted(pl, cmp=compare_point1)
[Point(x=0, y=4, z=9),
 Point(x=0, y=6, z=2),
 Point(x=1, y=9, z=5),
 Point(x=2, y=3, z=5),
 Point(x=3, y=7, z=1),
 Point(x=7, y=5, z=6),
 Point(x=7, y=9, z=4),
 Point(x=7, y=2, z=5),
 Point(x=8, y=1, z=2),
 Point(x=9, y=3, z=2)]

Na also, geht doch! Die eingebaute cmp-Funktion vereinfacht die Implementierung der Vergleichsfunktion erheblich. Auch diese Methode ist im Beispielmodul definiert und die entsprechende Vergleichsfunktion heißt compare_point2:

def compare_point2(p1, p2):
    return cmp(p1.x, p2.x)

>>> sorted(pl, cmp=compare_point2)
[Point(x=0, y=4, z=9),
 Point(x=0, y=6, z=2),
 Point(x=1, y=9, z=5),
 Point(x=2, y=3, z=5),
 Point(x=3, y=7, z=1),
 Point(x=7, y=5, z=6),
 Point(x=7, y=9, z=4),
 Point(x=7, y=2, z=5),
 Point(x=8, y=1, z=2),
 Point(x=9, y=3, z=2)]

Es kommt also das selbe Ergebnis heraus und ist bei großen Listen wahrscheinlich schneller, da cmp in C implementiert ist.

Das Decorate/Sort/Undecorate-Pattern

Das ist alles schön und gut, aber furchtbar umständlich. Wenn wir jetzt nicht nach dem x-Attribut sondern nach dem y- oder z-Attribut sortieren wollten, müssten wir jedesmal eine neue Vergleichsfunktion schreiben. Das muss doch auch einfacher gehen. Damit kommen wir zum Decorate/Sort/Undecorate-Pattern. Wie man am Namen sehen kann, besteht es aus drei Schritten.

  1. Erzeuge eine temporäre Liste aus Tupeln mit zwei Elementen: dem Wert, nach dem sortiert werden soll und das einzusortierende Objekt ("decorate"):
    >>> pltemp = [(p.x, p) for p in pl]
    >>> pltemp
    [(7, Point(x=7, y=5, z=6)),
     (1, Point(x=1, y=9, z=5)),
     (7, Point(x=7, y=9, z=4)),
     (0, Point(x=0, y=4, z=9)),
     (7, Point(x=7, y=2, z=5)),
     (8, Point(x=8, y=1, z=2)),
     (0, Point(x=0, y=6, z=2)),
     (9, Point(x=9, y=3, z=2)),
     (2, Point(x=2, y=3, z=5)),
     (3, Point(x=3, y=7, z=1))]
  2. Sortiere die temporäre Liste ("sort"):
    >>> pltemp.sort()
    >>> pltemp
    [(0, Point(x=0, y=6, z=2)),
     (0, Point(x=0, y=4, z=9)),
     (1, Point(x=1, y=9, z=5)),
     (2, Point(x=2, y=3, z=5)),
     (3, Point(x=3, y=7, z=1)),
     (7, Point(x=7, y=5, z=6)),
     (7, Point(x=7, y=9, z=4)),
     (7, Point(x=7, y=2, z=5)),
     (8, Point(x=8, y=1, z=2)),
     (9, Point(x=9, y=3, z=2))]
  3. Extrahiere die ursprünglichen Objekte aus der temporären, sortierten Liste ("undecorate"):
    >>> plsorted = [x[1] for x in pltemp]
    >>> plsorted
    [Point(x=0, y=6, z=2),
     Point(x=0, y=4, z=9),
     Point(x=1, y=9, z=5),
     Point(x=2, y=3, z=5),
     Point(x=3, y=7, z=1),
     Point(x=7, y=5, z=6),
     Point(x=7, y=9, z=4),
     Point(x=7, y=2, z=5),
     Point(x=8, y=1, z=2),
     Point(x=9, y=3, z=2)]

Ecco! Das Ganze geht ebenso einfach, wenn wir z.B. nach der y-Koordinate sortieren wollen (jetzt alle drei Schritte direkt hintereinander). Nur so zum Spaß kehren wir die Sortierreihenfolge diesmal um:

>>> pltemp = [(p.y, p) for p in pl]
>>>
>>> # Entweder:
>>> pltemp.sort()
>>> pltemp.reverse()
>>> # oder mit Python 2.4:
>>> pltemp.sort(reverse=True)
>>>
>>> psorted = [x[1] for x in pltemp]
>>> psorted
[Point(x=1, y=9, z=5),
 Point(x=7, y=9, z=4),
 Point(x=3, y=7, z=1),
 Point(x=0, y=6, z=2),
 Point(x=7, y=5, z=6),
 Point(x=0, y=4, z=9),
 Point(x=2, y=3, z=5),
 Point(x=9, y=3, z=2),
 Point(x=7, y=2, z=5),
 Point(x=8, y=1, z=2)]

Das Ganze geht natürlich auch in einem Schritt, sieht dann aber nicht mehr besonders schön aus (diesmal sortieren wir nach der z-Koordinate):

>>> [x[1] for x in sorted([(p.z, p) for p in pl])]
[Point(x=3, y=7, z=1),
 Point(x=9, y=3, z=2),
 Point(x=0, y=6, z=2),
 Point(x=8, y=1, z=2),
 Point(x=7, y=9, z=4),
 Point(x=2, y=3, z=5),
 Point(x=7, y=2, z=5),
 Point(x=1, y=9, z=5),
 Point(x=7, y=5, z=6),
 Point(x=0, y=4, z=9)]

Das key-Argument von sort

Puh, das kann ich mir ja nie merken! Geht das nicht noch einfacher? Jetzt kommt der Auftritt von Pythons geheimer, magischer Waffe ;-), das key-Argument von sort/sorted. Das sieht dann so aus:

>>> sorted(pl, key=lambda p: p.z)
[Point(x=3, y=7, z=1),
 Point(x=9, y=3, z=2),
 Point(x=0, y=6, z=2),
 Point(x=8, y=1, z=2),
 Point(x=7, y=9, z=4),
 Point(x=2, y=3, z=5),
 Point(x=7, y=2, z=5),
 Point(x=1, y=9, z=5),
 Point(x=7, y=5, z=6),
 Point(x=0, y=4, z=9)]

Wir sehen: das selbe Ergebnis. Wie funktionert das? Das key-Argument erwartet eine Funktion, die aus jedem einzusortierendem Objekt den Wert extrahiert, nach dem sortiert werden soll. Beispiel: key=str.lower. Diese Funktion ist oft sehr einfach und kann, wie in unserem Fall, mittels einer anonymen Funktion mit lambda implementiert werden.

Ein kleiner Wehrmustropfen bleibt allerdings: das key-Argument wird erst seit Python 2.4 unterstützt.

Ich überlasse es dem Leser als Übungsaufgabe, diese Methode auf die Sortierung unserer Liste nach der y-Koordinate anzuwenden.

Anwendungsbeispiel: ein Dictionary sortieren

So, das ist alles schön und gut, aber kann ich damit denn auch etwas Sinnvolles anfangen? Wie wäre es, wenn wir das Erlernte auf eine kleine Adressenliste anwenden, die im CSV-Format vorliegt? Die CSV-Beispieldatei ist als Anhang zu dieser Seite gespeichert.

Wir lesen die CSV-Datei mittel des csv-Moduls in ein Dictionary ein:

>>> import csv
>>> # Der csv.DictReader erwartet ein Dateiobjekt zum Lesen
>>> reader = csv.DictReader(open('sample.csv'))
>>> # Wir konvertieren den Iterator "reader" in eine Liste
>>> al = list(reader)
>>> al
[{'Email': 'h_mueller@web.de',
  'Name': 'Mueller',
  'Ort': 'Mannheim',
  'Strasse': 'Wilhem-Leuschner-Str. 34',
  'Vorname': 'Hans'},
 {'Email': 'susy@meier.de',
  'Name': 'Meier',
  'Ort': 'Aachen',
  'Strasse': 'Hauptstrasse 236',
  'Vorname': 'Sabine'},
 {'Email': 'treuter@gmx.net',
  'Name': 'Baumann',
  'Ort': 'Frankfurt',
  'Strasse': 'Reuterweg 16',
  'Vorname': 'Thorsten'},
 {'Email': 'inge_s@frankfurt.net',
  'Name': 'Schneider',
  'Ort': 'Frankfurt',
  'Strasse': 'Habsburger Allee 25',
  'Vorname': 'Inge'},
 {'Email': ' slehman34@hotmail.com',
  'Name': 'Lehmann',
  'Ort': 'Berlin',
  'Strasse': 'Gruener Pfad 7',
  'Vorname': 'Sieglinde'},
 {'Email': 'h.friedrich@pfalz.de',
  'Name': 'Friedrich',
  'Ort': 'Neustadt',
  'Strasse': 'Bachgasse 12',
  'Vorname': 'Hans'},
 {'Email': 'bschnei45@yahoo.de',
  'Name': 'Schneider',
  'Ort': 'Dortmund',
  'Strasse': 'Clemensstrasse 47',
  'Vorname': 'Bernd'},
 {'Email': '',
  'Name': 'Gruber',
  'Ort': 'Frankfurt',
  'Strasse': 'Mainzer Landstrasse 432',
  'Vorname': 'Dorothea'}]

Wir sortieren die Adressenliste nach dem Nachnamen:

>>> sorted(al, key=lambda x: x['Name'])
[{'Email': 'treuter@gmx.net',
  'Name': 'Baumann',
  'Ort': 'Frankfurt',
  'Strasse': 'Reuterweg 16',
  'Vorname': 'Thorsten'},
 {'Email': 'h.friedrich@pfalz.de',
  'Name': 'Friedrich',
  'Ort': 'Neustadt',
  'Strasse': 'Bachgasse 12',
  'Vorname': 'Hans'},
 {'Email': '',
  'Name': 'Gruber',
  'Ort': 'Frankfurt',
  'Strasse': 'Mainzer Landstrasse 432',
  'Vorname': 'Dorothea'},
 {'Email': ' slehman34@hotmail.com',
  'Name': 'Lehmann',
  'Ort': 'Berlin',
  'Strasse': 'Gruener Pfad 7',
  'Vorname': 'Sieglinde'},
 {'Email': 'susy@meier.de',
  'Name': 'Meier',
  'Ort': 'Aachen',
  'Strasse': 'Hauptstrasse 236',
  'Vorname': 'Sabine'},
 {'Email': 'h_mueller@web.de',
  'Name': 'Mueller',
  'Ort': 'Mannheim',
  'Strasse': 'Wilhem-Leuschner-Str. 34',
  'Vorname': 'Hans'},
 {'Email': 'inge_s@frankfurt.net',
  'Name': 'Schneider',
  'Ort': 'Frankfurt',
  'Strasse': 'Habsburger Allee 25',
  'Vorname': 'Inge'},
 {'Email': 'bschnei45@yahoo.de',
  'Name': 'Schneider',
  'Ort': 'Dortmund',
  'Strasse': 'Clemensstrasse 47',
  'Vorname': 'Bernd'}]

Seit Python 2.3 ist die Sortierung mit sort/sorted stabil, d.h. die Reihenfolge von zwei Elementen, deren Wert des Sortierkriteriums gleich ist, ändert sich durch die Sortierung nicht. Dies können wir ausnutzen, um die Adressenliste nach einem Hauptsortierkriterium (Name) und einem sekundären Sortierkriterium (Ort) zu sortieren. Wir sortieren zuerst nach dem sekundären Kriterium, dann nach dem Hauptkriterium (man beachte die Reihenfolge der beiden Schneiders in diesem und dem vorhergehenden Beispiel):

>>> albycity = sorted(al, key=lambda x: x['Ort'])
>>> sorted(albycity, key=lambda x: x['Name'])
[{'Email': 'treuter@gmx.net',
  'Name': 'Baumann',
  'Ort': 'Frankfurt',
  'Strasse': 'Reuterweg 16',
  'Vorname': 'Thorsten'},
 {'Email': 'h.friedrich@pfalz.de',
  'Name': 'Friedrich',
  'Ort': 'Neustadt',
  'Strasse': 'Bachgasse 12',
  'Vorname': 'Hans'},
 {'Email': '',
  'Name': 'Gruber',
  'Ort': 'Frankfurt',
  'Strasse': 'Mainzer Landstrasse 432',
  'Vorname': 'Dorothea'},
 {'Email': ' slehman34@hotmail.com',
  'Name': 'Lehmann',
  'Ort': 'Berlin',
  'Strasse': 'Gruener Pfad 7',
  'Vorname': 'Sieglinde'},
 {'Email': 'susy@meier.de',
  'Name': 'Meier',
  'Ort': 'Aachen',
  'Strasse': 'Hauptstrasse 236',
  'Vorname': 'Sabine'},
 {'Email': 'h_mueller@web.de',
  'Name': 'Mueller',
  'Ort': 'Mannheim',
  'Strasse': 'Wilhem-Leuschner-Str. 34',
  'Vorname': 'Hans'},
 {'Email': 'bschnei45@yahoo.de',
  'Name': 'Schneider',
  'Ort': 'Dortmund',
  'Strasse': 'Clemensstrasse 47',
  'Vorname': 'Bernd'},
 {'Email': 'inge_s@frankfurt.net',
  'Name': 'Schneider',
  'Ort': 'Frankfurt',
  'Strasse': 'Habsburger Allee 25',
  'Vorname': 'Inge'}]

So, das war's mit diesem Tutorium. Viel Spaß dabei, Ordnung in eure Daten zu bringen!

Tags: Codesnippets | Listen | Dict | Tipps

Sortierungs-Tutorium (zuletzt geändert am 2009-06-21 20:55:46 durch anonym)