Liste sortieren anhand einer anderen Liste

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Liste sortieren anhand einer anderen Liste

Beitragvon Jeremy » Donnerstag 11. Dezember 2008, 10:07

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
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Beitragvon jonas » Donnerstag 11. Dezember 2008, 10:31

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
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Beitragvon Jeremy » Donnerstag 11. Dezember 2008, 10:49

Hi jonas,

das ist genau das was ich gesucht habe!! :D

Vielen Dank!

Gruß Jeremy
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 11. Dezember 2008, 11:03

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]
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Beitragvon BlackJack » Donnerstag 11. Dezember 2008, 11:16

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__)
tordmor
User
Beiträge: 100
Registriert: Donnerstag 20. November 2008, 10:29
Wohnort: Stuttgart

Beitragvon tordmor » Donnerstag 11. Dezember 2008, 11:20

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]
Benutzeravatar
jonas
User
Beiträge: 156
Registriert: Dienstag 9. September 2008, 21:03

Beitragvon jonas » Donnerstag 11. Dezember 2008, 11:27

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 :D
MfG Jonas
BlackJack

Beitragvon BlackJack » Donnerstag 11. Dezember 2008, 13:22

@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.
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Beitragvon Jeremy » Donnerstag 11. Dezember 2008, 13:54

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.
BlackJack

Beitragvon BlackJack » Donnerstag 11. Dezember 2008, 17:15

@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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Donnerstag 11. Dezember 2008, 17:23

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.
Benutzeravatar
rudolfo.christ
User
Beiträge: 11
Registriert: Freitag 5. Dezember 2008, 18:47
Wohnort: Trier

Beitragvon rudolfo.christ » Donnerstag 11. Dezember 2008, 20:19

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.
BlackJack

Beitragvon BlackJack » Donnerstag 11. Dezember 2008, 23:13

@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).
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Beitragvon Jeremy » Freitag 12. Dezember 2008, 11:24

@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.
Benutzeravatar
rudolfo.christ
User
Beiträge: 11
Registriert: Freitag 5. Dezember 2008, 18:47
Wohnort: Trier

Beitragvon rudolfo.christ » Freitag 12. Dezember 2008, 14:49

@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).

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder