[Python-de] Listen vergleichen

Stefan Behnel behnel_ml at gkec.informatik.tu-darmstadt.de
Mit Jun 28 12:12:16 CEST 2006


Hi Martin,

Martin v. Löwis wrote:
> Stefan Behnel wrote:
>> Wobei vielleicht erwähnt werden sollte, dass diese Varianten a) in C ablaufen
>> und b) nicht quadratisch - O(N*M) - sind wie verschachtelte Schleifen, sondern
>> O(N+M), da intern Hashing verwendet wird. Sollten also sehr effizient sein.
> 
> Das gibt mir wieder Anlass zu meiner Lieblings-Tirade: Hash-Operationen
> sind, im schlechtesten Fall, *nicht* in O(1).

Genauso wenig, wie die Variante mit verschachtelte Schleifen im schlechtesten
Fall O(N*M) ist. Die hängt nämlich z.B. auch vom Aufwand der
Vergleichsfunktionen ab. Wenn ich da irgendwelche rekursiven Datenstrukturen
durchlaufen muss, um festzustellen, dass die beiden Objekte identisch sind,
dann ist die Komplexität schnell mal eben explodiert (da eben auch quadratisch
verwendet).

Jedenfalls ist die Wahrscheinlichkeit, dass ich mit "set(l1).intersection(l2)"
(guter Vorschlag übrigens) besser bedient bin als mit "for-for-Vergleich",
doch ausreichend groß. Insbesondere in dem konkreten Beispiel mit Zahlen, die
sicherlich keine allzu aufwändige hash-Funktion haben. Und auch deshalb, weil
ich bei Bedarf durch einfache Implementierung einer geeigneteren Hash-Funktion
für meine Objekte die wichtigsten der von dir genannten Probleme umgehen kann
(sogar per Versuch-macht-kluch). Die Komplexität von verschachtelten Schleifen
zu ändern ist da nicht ganz so einfach.

Stefan