Problem bei Multi-Sortierung von dict-liste

[stagger]

Hallo zusammen,

für den Titel muss ich mich entschuldigen, aber sollte ja halbwegs aussagekräftig sein Dazu sei gesagt: Ich bin totaler Python-Neuling und nur zu der Sprache gekommen, weil Excel-Makros zu langsam für den Job sind und Python ein gutes CSV-Import-Modul hat. Ich muss nämlich 150.000+ Zeilen ordentlich in die Mangel nehmen. Freude. Jetzt gerade häng ich aber und komme ohne Hilfe nicht weiter.

Ich lese die CSV-Datei problemlos ein, übernehme die Zeilen als Dictionary in eine Liste und entferne die Werte, die mir nicht passen. Anschließend möchte ich die Liste sortieren, und zwar anhand mehrerer Schlüssel (Bestellnummer, Bestellposition, Bearbeitungsreihenfolge). Dazu habe ich Quicksort implementiert und eine weitere Funktion sort() geschrieben, die quicksort() mit der zu sortierenden Liste und den Sortierkriterien aufruft.

In der Funktion sort() werden die Schlüssel einer nach dem anderen durchlaufen. Ist es der erste Schlüssel, wird die Liste vollständig sortiert. Danach werden erst Teilbereiche festgelegt, über die nach dem Unterschlüssel sortiert werden soll, und dann für diese Teilbereiche noch einmal quicksort() aufgerufen. Das klappt soweit auch ganz gut. Nach dem ersten Durchlauf ist die Liste nach dem ersten Schlüssel sortiert. Nach dem zweiten Durchlauf ist die Liste nach dem ersten und zweiten Schlüssel sortiert. Nach dem dritten Durchlauf jedoch ist die Liste nur noch nach dem ersten und dritten Schlüssel sortiert. Anschaulich:

Rohmaterial:

07SO00102 , 1 , 03 B1
06SO06950 , 1 , 03 B1
05SO06118 , 1 , 03 B1
07SO00105 , 1 , 03 B1
06SO06949 , 1 , 03 B1
04SO00710 , 1 , 03 B1
04SO00708 , 1 , 03 B1
03SO03948 , 1 , 03 B1
07SO00063 , 1 , 03 B1
06SO04419 , 1 , 03 B1

Nach zweitem Durchlauf:

02SA00002 , 1 , 3 01
02SA00002 , 1 , 4 01
02SA00002 , 1 , 2 01
02SA00002 , 1 , 1 01
02SA00002 , 3 , 2 01
02SA00002 , 3 , 3 01
02SA00002 , 3 , 1 01
02SA00002 , 3 , 4 01
02SA00002 , 4 , 1 2
02SA00002 , 4 , 1 1

Nach drittem Durchlauf:

02SA00002 , 3 , 1 01
02SA00002 , 1 , 1 01
02SA00002 , 4 , 1 1
02SA00002 , 4 , 1 2
02SA00002 , 3 , 2 01
02SA00002 , 1 , 2 01
02SA00002 , 1 , 3 01
02SA00002 , 3 , 3 01
02SA00002 , 1 , 4 01
02SA00002 , 3 , 4 01

Der Einfachheit halber stell ich mal den ganzen Code ein. Der Aufruf der Sortierfunktion erfolgt beim ersten Block ganz unten.

analysis.py: http://paste.pocoo.org/show/11448/
quicksort.py: http://paste.pocoo.org/show/11449/

Falls ich die langen Zeilen das nächste Mal umbrechen soll, bitte kurz Bescheid sagen. Ich hab jetzt keine Lust mehr die Forenregeln oder Ähnliches zu lesen, weil's hier doch schon recht spät ist und ich auch gern mal nach Hause würd'

Bin für jede Hilfe dankbar! Wenn's schon ein Modul gibt, das erledigt, was ich haben will, bin ich auch gern bereit das statt meinem Gefrickel zu benutzen. Immer her damit

Edit (BlackJack): Quelltext ausgelagert.

[Rebecca]

1.) Wo ist die Frage?

2.) Ich habe deinen Code nur so grob ueberflogen, aber Dicts kann man nicht sortieren.

3.) Lies dir mal das hier durch: [wiki]Sortierungs-Tutorium[/wiki]

4.) So langen Code bitte in eine NoPaste-Service auslagern, denn das Forum hat damit Probleme

[BlackJack]

So ich habe den Quelltext mal ausgelagert. Lange Zeilen umbrechen ist 'ne gute Idee. Das ist zwar keine feststehende Regel hier im Forum, aber es gibt Browser, die auch den Text so breit machen wie die längste Zeile im Quelltext und man muss dann horizontal scrollen um den Beitrag zu lesen. Das ist recht mühselig.

Mein erster Gedanke: Da hat sich jemand ein Quicksort selbst geschrieben!? Wahnsinn!

Es gibt auf Listen eine `sort()`-Methode die entweder die Objekte befragt ob sie grösser oder kleiner als andere in der Liste sind, oder man kann eine Schlüsselfunktion angeben, die für jedes Objekt in der Liste einen Wert berechnet nach dem dann letztendlich sortiert wird. Als dritte Möglichkeit kann man noch eine eigene Vergleichsfunktion angeben.

Diese Methode hat auch noch eine Eigenschaft, die Deine Funktion (Quicksort) im allgemeinen nicht hat: sie ist stabil d.h. Elemente die "gleich" sind, verändern beim Sortieren ihre Reihenfolge nicht.

Wobei Du natürlich versuchen kannst gleich in einem Sortiervorgang nach mehreren "Spalten" zu sortieren.

[stagger]

2.) Ich habe deinen Code nur so grob ueberflogen, aber Dicts kann man nicht sortieren.

Es geht nicht darum, Dicts zu sortieren, sondern eine Liste von Dicts, und zwar mit Priorisierung bestimmter Schlüssel.

Mein erster Gedanke: Da hat sich jemand ein Quicksort selbst geschrieben!? Wahnsinn!

Die Jemande heißen eigentlich James Gosling und Kevin A. Smith Dass Quicksort nicht stabil ist, macht überhaupt nichts, da die Liste keine gleichen Elemente hat.

Die Hinweise zu NoPaste und Umbruch merk ich mir. Safari hat damit ja z.B. Probleme.

Die Übergabe einer Sortierfunktion teste ich mal und stell dann den Code hier ein, sobald es funktioniert. Sollte auch wesentlich kürzer sein

Besten Dank!

[stagger]

Code: Alles auswählen

def cmp_dicts(dict1, dict2):
    "Compare by list of keys (1: ascending; -1: descending)"
    for key in cmp_dicts_keys:
        if dict1[key[0]] < dict2[key[0]]:
            return key[1] * -1
        elif dict1[key[0]] > dict2[key[0]]:
            return key[1]
    return 0


cmp_dicts_keys = [("sorder", 1), ("soitem", 1), ("opseq", 1)]
filtered.sort(cmp_dicts)

Das ging aber bedeutend einfacher

[BlackJack]

Ich hatte "gleich" in Anführungszeichen gesetzt, weil es hier nur um Gleichheit auf den Sortierschlüssel bezogen geht. Und das ist das Problem wenn man mit Quicksort nacheinander nach mehreren Schlüsseln sortiert. Weil's nicht stabil ist, können vorher nach Kriterium A sortierte Zeilen wieder durcheinandergewürfelt werden wenn sie nach Kriterium B gleich sind. Beispiel:

Code: Alles auswählen

c 42
c 23
a 23
b 23
b 42
a 42

Sortiert nach Buchstaben:

Code: Alles auswählen

a 23
a 42
b 23
b 42
c 42
c 23

Und wenn man jetzt nach den Zahlen sortiert, dann garantiert ein stabiles Sortierverfahren, dass alle Zeilen mit der gleichen Zahl weiterhin relativ zu einander in der gleichen Reihenfolge bleiben:

Code: Alles auswählen

a 23
b 23
c 23
a 42
b 42
c 42

Während bei nicht-stabilen Verfahren wie Quicksort die Zeilen mit gleichen Zahlen wieder ihre Sortierung vom ersten Durchlauf verlieren können, also z.B. folgendes dabei herauskommt:

Code: Alles auswählen

b 23
a 23
c 23
a 42
c 42
b 42

Bei der Vergleichsfunktion sollten die Schlüssel und Reihenfolgen Argumente sein und die Indexe machen das etwas unleserlich, da sollte man in der Schleife Namen für die beiden Elemente vergeben. Ansonsten kann man auch noch auf die `cmp()`-Funktion zurückgreifen.

Code: Alles auswählen

def cmp_dicts(dict1, dict2, keys_and_order):
    """Compare by list of keys (1: ascending; -1: descending)"""
    for key, order in keys_and_order:
        tmp = cmp(dict1[key], dict2[key])
        if tmp != 0:
            return tmp * order
    return 0

[stagger]

Weil's nicht stabil ist, können vorher nach Kriterium A sortierte Zeilen wieder durcheinandergewürfelt werden wenn sie nach Kriterium B gleich sind.

Ah, ok. Jetzt hat's Klick gemacht

Danke für den Tipp mit der CMP-Funktion. Ich bin schon gespannt, wie viel Arbeit ich mir im Rückblick noch hätte sparen können, wenn ich nur die entsprechenden Python-eigenen Funktionen gekannt hätte. Aber dazu lernt man ja