@Leonidas:Von der Sicht betrachtet hast du selbstverständlich recht.
birkenfeld hat geschrieben:
*seufz* Es ist egal, was du da findest, es ist objektiv so, dass die Variante mit Listen schlechteres Laufzeitverhalten als die mit Mengen hat.
Habe ich was anderes Behauptet? Ich hab nicht geschrieben das `list`\s eine besseres Laufzeitverhalten haben als `set`\s. Ich habe lediglich geschrieben das es IMHO trotz seines Arguments performant genug ist und die Iteration in beiden Fällen linear ist. Zu dem ``f x not in other`` test siehe unten.
birkenfeld hat geschrieben:
Das Iterieren ist linear, ja. Der Check "if x not in other" ist für Mengen konstant, für Listen allerdings wieder linear -- damit baust du einen quadratischen Algorithmus.
Ups, stimmt, mein Fehler. Der ``if x not in other`` test ist auch linear, da in ``other`` jedes Element mit ``x`` verglichen wird bis eine Übereinstimung gefunden wurde. -- Das habe ich übersehen.
Das der ``in`` test von einem `set` Konstant ist wusste ich nicht. Ich hab gerade nochmal in der
Dokumentation geschaut und da steht das für die Implementation des `set`\s ein `dict` benutzt wird, dessen lookup ja auch Konstant ist.
birkenfeld hat geschrieben:
Der zweite Operand muss hierfür keine Liste sein.
Code: Alles auswählen
def minus(a, b):
b = set(b)
return [x for x in a if x not in b]
So, bis hier hin gebe ich dir absolut Recht, aber dieser Vorschlag grenz jetzt an Lächerlichkeit.
1. Gerade weil ein `set` ein `dict`für die Verbesserung des lookups nutzt, können nur imutables benutzt werden:
Code: Alles auswählen
>>> set([1, 2, 3])
set([1, 2, 3])
>>> set([1, 2, [3]])
Traceback (most recent call last):
File "<pyshell#1>", line 1, in <module>
set([1, 2, [3]])
TypeError: list objects are unhashable
>>>
2. Wenn ich deinen Vorschlag richtig interpretiere willst du sagen, dass man bei jeden Code der ``if x in other`` benutzt, immer ``other`` erst in ein `set` umwandeln sollte. Dein Vorschlag kann ich nicht generell empfehlen weil dein Code bei imutablen Elementen nicht funktioniert.
In allen andere fällen wo man 100% ausschließen kann das ``other`` imutables beinhaltet, ist das natürlich okay. Aber, hmm, da frage ich mich ob man es nicht etwas mit der voreiligen Optimierung übertreibt? Siehe dazu auch 3.
3.
http://en.wikipedia.org/wiki/Optimizati ... ce)#Quotes
Michael A. Jackson hat geschrieben:The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.