[Python-de] Listen vergleichen

Stefan Schwarzer sschwarzer at sschwarzer.net
Die Jun 27 13:21:04 CEST 2006


Hallo Stefan,

On 2006-06-27 12:28, Stefan Behnel wrote:
> Stefan Schwarzer schrieb:
>> On 2006-06-27 11:35, Julian Rath wrote:
>>> habe hier 2 Listen und möchte vergleichen ob ein element der einen in
>>> der anderen vorhanden ist. wie das mit einer schleife löse wes ich.
>> def have_common_elements(list1, list2):
>>     return bool(set(list1) & set(list2))
>>
>> Wenn du eine (unsortierte) Liste der gemeinsamen Elemente
>> haben willst:
>>
>> def common_elements(list1, list2):
>>     return list(set(list1) & set(list2))
>
> Wobei vielleicht erwähnt werden sollte, dass diese Varianten a) in C ablaufen

_Diese_ Varianten ja, das sets-Modul aus Python 2.3 nicht bzw.
nur der Teil davon, der von eingebauten Datentypen übernommen
wird.

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

Apropos Hashing, dazu ist ggf. noch zu beachten:

http://docs.python.org/lib/types-set.html bzw.
http://docs.python.org/lib/immutable-transforms.html

Enthalten die Listen bspw. nur Zahlen (wie in Julians Frage) oder
Zeichenketten, muss man das nicht lesen, aber wenn die Listen
Elemente enthalten, die "mutable" sind, hat man u. U. ein
Problem. Davon abgesehen, ist der Effizienzvorteil vermutlich
nicht so wichtig, wenn die Listen recht klein sind. Man bemühe
einen Profiler, falls das Programm _zu_ langsam ist. :-)

Viele Grüße
Stefan