AW: [Spam 42,42%] [Python-de] Listenvergleich

Diez B. Roggisch deets at web.de
Fre Jan 28 15:02:27 CET 2005


>
> def contains (ls1, ls2):
>   for e in ls2:
>    if e not in ls1:
>     return False
>   return True

Das ist die denkbar schlechteste Loesung von der Performance her - denn die 
ist ueblicherweise irgendwas mit O(n * m) mit

n, m = len(ls1) , len(ls2)


 Die Loesung mit sets ist O(mm * log(mm)) mit 

mm = max([m,n])

Ab python 2.4 ist sets ausserdem in C geschrieben, und falls er solche 
Vergleiche oefter hat,  ist natuerlich der Aufwand fuer die Erzeugung des 
sets nur einmal zu berechnen, womit sich die Performance auf O(mm) 
verbessert.

Das mag alles nach Korinthenkackerei aussehen - aber quadratische Algorithmen 
fallen einem schneller auf die Fuesse als es einem lieb sein kann.

MfG Diez