[Python-de] Listen vergleichen

"Martin v. Löwis" martin at v.loewis.de
Mit Jun 28 10:44:35 CEST 2006


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). Vielmehr hängt die
Komplexität ab von
a) der Rechenzeit/Komplexität der hash-Operation
b) der Rechenzeit/Komplexität der Vergleichsoperation
c) der Häufigkeit von Kollisionen

Gerade Punkt c) kann leicht die Leistung von Hash-Tabellen verderben:
wenn beispielsweise viele Schlüssel den gleichen Hashwert haben, dann
wird die Leistung deutlich schlechter.

Für das konkrete Problem kommt noch d) hinzu:

d) den Kosten für die Vergrößerung der Hashtabelle

Im konkreten Problem kann man noch dadurch sparen, dass man eine
der beiden Listen nicht in eine Menge konvertiert, etwa

def have_common_elements(l1, l2):
  return bool(set(l1).intersection(l2))

.intersection iteriert über l2; dazu muss man nicht vorab eine
Menge konstruieren.

Ciao,
Martin