Das deutsche Python-Forum

Hallo zusammen,

zum Thema Listen sortieren habe ich schon mal eine Frage gestellt, jetzt kommt die Nächste.

Ich habe 2 Listen z.B.: A = [2,9,1,5,3,6] und B = [9,2,5] (jeder Listeneintrag kommt nur einmal in jeder Liste vor).
Nun möchte mit der Listenmethode sort() die Liste B so sortieren, dass die Elemente in der Reihenfolge wie sie in Liste A stehen sortiert werden: also irgendwie so: B.sort(A) ???? und als Ergebnis soll raus kommen: B = [2,9,5].

Oder geht das nur mit einer for-Schleife über A und mit if A[x] in B...?

Gruß Jeremy

Hi Jeremy,
hab hier kurz was gebastelt, müsste gehen:

Code: Alles auswählen

#!/usr/bin/python
## listeanhandvonliste.py

def sortbylist (listtosort,sortinglist):
    result = []
    for i in range(len(sortinglist)):
        if sortinglist[i] in listtosort:
            result.append(sortinglist[i])
    return result
    
if __name__ == "__main__":
    liste1 = [2,9,1,5,3,6]
    liste2 = [9,2,5]
    liste2 = sortbylist(liste2,liste1)
    print liste2

bringt bei mir:

Code: Alles auswählen

>python -u "listeanhandvonliste.py"
[2, 9, 5]

Hoffe dir geholfen zu haben

MfG Jonas

Hi jonas,

das ist genau das was ich gesucht habe!!

Vielen Dank!

Gruß Jeremy

Also irgendwie verstehe ich die Ordnung nicht ganz. Wenn man zwei gleichlange Listen hat und die Sortierung an die zweite Liste binden will würde man mit (i)zip Tupelpaare bauen und nach der zweiten Liste sortieren und dann die Tupel wieder zerlegen. Bei dir scheint das nicht der Fall zu sein, es sieht eher aus als würde man bei dir die Liste A filtern nach Einträgen die in der anderen Liste vorkommen.

Code: Alles auswählen

print [e for e in A if a in B]

Also ich verstehe die Ordnung so, dass der Index eines Elements in der zweiten Liste der Sortierschlüssel ist. Wenn man das also mit Sortieren lösen möchte:

Code: Alles auswählen

def sort_by_list(to_sort, reference_list):
    keys = dict((item, index) for index, item in enumerate(reference_list))
    to_sort.sort(key=keys.__getitem__)

Code: Alles auswählen

>>> A = [2,9,1,5,3,6]
>>> B = [9,2,5]
>>> sorted(B, cmp=lambda x,y: cmp(A.index(x), A.index(y)))
[2, 9, 5]

Hi,
ja stimmt schon, das bei mir mehr gefiltert als sortiert wird.
Da könnten auch mal Elemente verloren gehen...
Naja ist ja egal, mittlerweile sind ja genug Lösungen da

MfG Jonas

@tordmor: Ganz übles Laufzeitverhalten. Bei jedem Vergleich wird die Vergleichsfunktion aufgerufen und dann beide Objekte jeweils *linear* in `A` gesucht.

Wenn möglich sollte man immer `key` statt `cmp` verwenden. In Python 3.0 gibt's `cmp` auch nicht mehr.

Hintergrund ist, ich habe 2 Llisten A und C, sie enthalten Tupel als Koordinatenpaare (x,y).
Aus diesen Listen wird die Schnittmege ermittelt, das läuft über sets (-> Reihenfolge der Koordinatenpaare geht verloren).
Die Schnittmenge wird wieder zur Liste (hier B) und diese Liste soll dann so sortiert werden, dass die punkte die Reihenfolge haben, die sie auch in Liste A haben.
Da hilft mir der Vorschlag von Jonas weiter.

Aber mir kommt noch eine weiterführende Frage: Wie groß ist der Aufwand, um die Sortierfunktion in der Form B.sortbylist(A) aufzurufen?
Muss man sortbylist dann als Methode von Listen implementieren?

PS: Mit Python arbeite ich erst seit ca. 8 Wochen, nutze Python als Skriptsprache in Abaqus (FEM-Software). Ein "gelernter"
Informatiker bin ich nicht.

@Jeremy: Du solltest vielleicht die Schnittmenge schon "sortiert" erstellen, also nicht beide Listen in `set()`\s umwandeln, sondern nur eine und das Ergebnis dann per "list comprehension" bilden.

Jeremy hat geschrieben:Hintergrund ist, ich habe 2 Llisten A und C, sie enthalten Tupel als Koordinatenpaare (x,y).

Ich verstehe jetzt nicht, was hier gegenüber dem letzten Thread dazu neu ist, da dein damals geschildertes Problem ja gelöst worden ist.

Aber mir kommt noch eine weiterführende Frage: Wie groß ist der Aufwand, um die Sortierfunktion in der Form B.sortbylist(A) aufzurufen?

Der Aufwand ist O(m * n), da wie BlackJack schon anmerkte die Listen "linear" durchlaufen werden, aber eben mehrmals.

Bei dem kleinen Bespiel kein Grund zur Sorge, aber wenn die Listen wachsen, hat dein Rechner ganz schön was zu tun.

Wenn es dir rein um die Schnittmenge geht, auf jeden Fall zuerst die Listen mit einem (guten) Sortieralgorithmus sortieren. Denn von sortierten Listen eine Schnittmenge zu bilden ist mit Aufwand von O(n) zu realisieren. Und das macht sich ab einer gewissen grösse der Listen bemerkbar.

@rudolfo.christ: Sortieren ist zu aufwändig. Von einer Liste ein `set` erstellen und dann über die andere iterieren und nur die Elemente in das Ergebnis aufnehmen, die im `set` sind läuft in O(n + m).

@numerix: die hier gestellte Frage kam auf, als ich eine Liste mit L.sort() sortierte. Und da kam mir die Idee, ob man beim Sortieren auh eine Referenzliste vorgeben kann, damit das im Code nachher einfacher zu erkennen ist, was gemacht wird. Eine Funktion selbst zu definieren ist damit die Antwort auf die gestellte Frage. Vielleicht etwas unglücklich gestellt.
Wie ich die Listen abarbeite ist in dem von dir genannten Thread beantwortet worden.

@BlackJack:

das wird aber nur funktionieren wenn beide Listen aufsteigend sortiert sind. Dann braucht man beide Listen nur genau einmal zu durchlaufen.

Wenn ich sets aus den Listen mache und dann über beide iteriere bin ich immer noch bei O(n*m) da ich für jedes Element in Liste (oder set) A, Liste B komplett durchlaufen muss (also im worst-case, wenn keines der Element in Liste B ist).

Das kann man durch Sortierung verhindern.

Der Knackpunkt ist das Schlüsselwort "in". Um zu zeigen das eine Element in einder verketteten Liste ist, ist der Aufwand O(n).

@rudolfo.christ: Die Listen brauchen nicht sortiert zu sein, sollten sie auch gar nicht, weil man sie danach ja dann wieder "teuer" in die orgininale Reihenfolge bringen müsste.

Liste A in ein `set` umwandeln: O(n). Aus Liste B mit Rückgriff auf das `set` alle unerwünschten Elemente filtern: O(m). Beides nacheinander ausführen: O(n+m).

Code: Alles auswählen

tmp = set(A)
result = [x for x in B if x not in tmp]

Ich weiss nicht wie Du da auf O(n*m) kommst!?

Nebenbei: ``in`` auf Listen hat lineare Laufzeit, aber `list` ist nicht als verkettete Liste implementiert.

@BlackJack

Die Listen brauchen nicht sortiert zu sein, sollten sie auch gar nicht, weil man sie danach ja dann wieder "teuer" in die orgininale Reihenfolge bringen müsste.

Deshalb bezog sich meine Annmerkung auch alleine auf Schnittmengen. Und da bei Mengen die Reihenfolge irrelevant ist, kann man die Listen getrost sortieren bevor man die Schnittmenge bildet.

Nebenbei: ``in`` auf Listen hat lineare Laufzeit, aber `list` ist nicht als verkettete Liste implementiert.

und linear ist die Komplexitätsklasse O(n). Durch die Indizierung (und falls die Liste sortiert sein sollte) schafft man die member-Operation sogar mit logarithmischen Aufwand. (Binäre Suche).

Ich versuche jetzt nochmal zu verdeutlichen wie ich O(n^2) komme:

a = [5,8,2,7,9], |a| = 5
b = [9,2,6,4], |b| = 4

Wenn ich jetzt das Beispiel von dir neheme heisst das:
Für alle x aus a, wenn x nicht aus b, dann mach irgendetwas. D.h. das für jedes x das man aus a nimmt, muss jedes Element aus b betrachtet werden, um entscheiden zu können ob x wirklich nicht in b ist.

Im Endeffekt werden |b| viele Elemente |a| mal betrachtet. Daraus folgt ein Aufwand von O(|a| * |b|). Sollte jetzt der Bertag von a ungefähr gleich dem Betrag von b sein, haben wir O(n^2), also quadratische Laufzeit.

Nimmt man es jetzt in Kauf die Listen erst zu sortieren (bei einem guten Sortierverfahen wie Merge Sort oder Heap Sort bei einer Komplexität von O(n * log n) ) lässt sich die Schnittmenge mit linearen (O(n)) Aufwand bilden, denn dann können beide Listen parallel durchlaufen werden.
Und O(n * log n) + O(n) ist immer noch effizienter als O(n^2) und das für alle c aus N für n0 = 1.

@rudolfo.christ: Viel blabla was gar nichts mit der Aufgabenstellung zu tun hat. Ich hatte eine Vorgehensweise beschrieben und gesagt dass die in O(n+m) Zeit läuft, was Du bestritten hast. Ich will nicht wissen ob Du eine O(n*m)-Lösung konstruieren kannst, die noch nicht einmal das Problem löst, sondern wo meine Lösung zum eigentlichen Problem angeblich nicht in O(n+m) läuft und sortierte Listen benötigen soll!?

@BlackJack

Code: Alles auswählen

tmp = set(A)
result = [x for x in B if x not in tmp]

Das läuft nicht linear. Wenn "in" auf Listen linear läuft und du für mehrere x überprüfst ob x nicht in tmp ist, dann bist du schon bei quadratischen Aufwand.
Dann ist es auch vollig egal ob set(A) linear läuft oder nicht. Wie in meinem Bespiel oben schon erwähnt. Für jede neue Iteration, bei der dein x sich verändert, betrachtest du A L L E Element von tmp.

Und bevor du noch unverschämter wirst, weise ich nochmals darauf hin, dass ich mich rein auf die Schnittmenge bezogen habe. Und in einer Menge spielt die Reihenfolge keine Rolle. Soll die Reihenfolge erhalten bleiben, dann darf man natürlich nicht sortieren, aber das stand sowieso nie zur Debatte

Die beiden Befehle lassen sich in'ne normale Schleife übersetzen, nicht in 2 verkettete Schleifen. Die erste Schleife läuft linear und ihr Körper besteht nur aus einem Befehl (an das set anhängen), der beschränkt ist. 1 * n also...

Der 2te Befehl is auch nur'ne lineare Schleife, mit einer Abfrage, die beschränkt ist und im Abgfragenkörper ein Befehl (auch wieder an die Liste anhängen) der beschränkt ist. Damit is's 1*1*n...

Für mich ist das 1*n+1*1*n.. Nach'r Groß-O-Notation ist das wohl ein simpler linearer Aufwand...

(Vorrausgesetzt wir nehmen die Länge der Liste als Problemgröße, aber das tut wohl jetzt nix zur Sache)

Das deutsche Python-Forum

Liste sortieren anhand einer anderen Liste

Liste sortieren anhand einer anderen Liste