Hallo 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. aber giebt es das einen kleinen weg? a=[1,2,3,4,5,6] b=[5,8] sollte True ergeben a=[1,2,3,4,5,6] b=[8,10] sollte False ergeben thx Julian -- *********************************** Julian Rath abacon GmbH austria Wagnereg 26 8054 Graz AUSTRIA tel: +43 316 255536 - 22 fax: +43 316 255536 - 3 _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Julian Rath wrote:
Wie war das noch mit Mengenlehre? ;-) Du könntest prüfen, ob die Mächtigkeit der Schnittmenge größer 0 ist: len(set(a).intersection(set(b))) > 0 -- Gerhard _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Julian, On 2006-06-27 11:35, Julian Rath wrote:
wenn ich dein Problem richtig verstanden habe, sowas wie: 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)) Läuft so ab Python 2.4, unter 2.3 musst du das Modul sets importieren und sets.Set statt set verwenden. Viele Grüße Stefan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo, Stefan Schwarzer schrieb:
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. Stefan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Stefan, On 2006-06-27 12:28, Stefan Behnel wrote:
_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 _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Stefan Behnel wrote:
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 _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Martin, Martin v. Löwis wrote:
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 _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Julian Rath wrote:
Wie war das noch mit Mengenlehre? ;-) Du könntest prüfen, ob die Mächtigkeit der Schnittmenge größer 0 ist: len(set(a).intersection(set(b))) > 0 -- Gerhard _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Julian, On 2006-06-27 11:35, Julian Rath wrote:
wenn ich dein Problem richtig verstanden habe, sowas wie: 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)) Läuft so ab Python 2.4, unter 2.3 musst du das Modul sets importieren und sets.Set statt set verwenden. Viele Grüße Stefan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo, Stefan Schwarzer schrieb:
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. Stefan _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hallo Stefan, On 2006-06-27 12:28, Stefan Behnel wrote:
_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 _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Stefan Behnel wrote:
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 _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
Hi Martin, Martin v. Löwis wrote:
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 _______________________________________________ python-de maillist - python-de@python.net http://python.net/mailman/listinfo/python-de
participants (5)
-
"Martin v. Löwis" -
Gerhard Häring -
Julian Rath -
Stefan Behnel -
Stefan Schwarzer