Liste sortieren anhand einer anderen Liste

[BlackJack]

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

[rudolfo.christ]

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

[BlackJack]

@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!?

[rudolfo.christ]

@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

[BlackVivi]

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)

[BlackJack]

@rudolfo.christ: Und ob das in linearer Zeit läuft. Der Test mit ``in`` ist ja nicht auf einer Liste, sondern auf einem `set`, welches als Hashtabelle implementiert ist, und damit läuft der Test auf "enthalten sein" in O(1) Zeit ab. Und die "list comprehension" läuft damit in linearer Zeit.

Was bei ``in``-Operator passiert hängt vom Objekt auf der rechten Seite ab, denn ``a in b`` ist letztendlich das gleiche wie ``b.__contains__(a)``, sofern der Typ von `b` die `__contains__()`-Methode implementiert.

Ich will nicht unverschämt sein, oder werden -- bin einfach nur ein wenig ungeduldig, wenn Du dauernd etwas falsches behauptest und so uneinsichtig bist.

[rudolfo.christ]

@BlackJack

Okay. Wenn "set" als Hashtabelle implementiert ist, dann zeige ich mich einsichtig. Dises Information blieb mir bis jetzt vorenthalten. Dann hast du Recht und der Algorithmus läuft mit linearen Aufwand.

Dennoch ist das von mir oben geschilderte nicht gänzlich falsch. Gilt eben nur nicht für sets in Python.