was ist schneller oder sonstwie besser?

[Goswin]

Ich habe oft die Wahl zwischen Ausdrücken wie (if-Bedingung ist nur ein Beispiel):

Code: Alles auswählen

len(paar for paar in paar_dict.items() if paar[0]==paar[1])

und

Code: Alles auswählen

len(x0 for (x0,x1) in paar_dict.items() if x0==x1)

Welches der beiden ist vorzuziehen? Oder ist es egal?
(Python-Folklore sagt ja, es solle möglichst immer nur eine offensichtliche Art geben )

[BlackJack]

@Goswin: Also *schneller* dürfte problematisch werden, denn der `TypeError` weil Generatoren keine `__len__()`-Methode haben kommt ja quasi *sofort*.

Ich würde sagen sinnvolle Namen sind in der Regel besser lesbar als Indexzugriffe weil man dem Leser mit den Namen mehr Informationen rüberbringen kann. Also ``sum(1 for k, v in paar_dict.iteritems() if k == v)`` mit sinnvollen Namen für `k` und `v` würde ich bevorzugen.

[Goswin]

BlackJack schreibt:

Sinnvolle Namen sind in der Regel besser lesbar als Indexzugriffe

Alles klar, vielen Dank!
(und natürlich müssen die Klammern eckig sein)

[BlackJack]

@Goswin: Naja, eckige Klammern nur wenn man tatsächlich die Liste erstellen möchte, was man nur für's zählen ja nicht unbedingt tun muss.

[snafu]

Wenn es um Performance geht, dann würde ich den Schritt über das Schlüssel-Wert-Iterator weglassen und direkt über die Schlüssel des Dictionaries iterieren. Die Werte bekomme durch Abfrage des Dictionaries mit dem jeweiligen Schlüssel. Sähe dann so aus:

Code: Alles auswählen

sum(1 for key in paar_dict if key == paar_dict[key])

Bei meinem Test-Dictionary mit 3 gleichen und 3 unterschiedlichen Schlüssel-Wert-Paaren war dies unter Python 3.4 die schnellere Variante. Weiter habe ich jetzt nicht getestet.

EDIT: Bei größeren Dictionaries mit ähnlicher 50%-Verteilung liegt BlackJacks Variante knapp vorne. Im Endeffekt dürfte es – wie so oft - ziemlich egal sein, welche Variante man benutzt, da beide bereits gut optimiert sind.

[Üpsilon]

Code: Alles auswählen

sum(1 for key in paar_dict if key == paar_dict[key])

Man kann Wahrheitswerte auch addieren (True+True ergibt 2). Deswegen geht auch das:

Code: Alles auswählen

sum(k==d[k] for k in d)

Ohne es getestet zu haben, glaube ich, dass das n bissl schneller ist.

[snafu]

Man kann Wahrheitswerte auch addieren (True+True ergibt 2). Deswegen geht auch das:

Code: Alles auswählen

sum(k==d[k] for k in d)

Ohne es getestet zu haben, glaube ich, dass das n bissl schneller ist.

Das ist mir bekannt und diese Idee hatte ich auch schon ausprobiert. Es hat sich aber gezeigt, dass hier sozusagen alle Elemente aus der List Comprehension herauskommen und dies langsamer ist, als wenn man bereits in der LC filtert und nur zutreffende Elemente auswirft. Wenn du testen willst, dann empfehle ich IPython, weil du in dessen Shell nur ein "timeit" vor den Python-Ausdruck schreiben muss und schon macht IPython eine Zeitmessung für dich.

Wie gesagt: Naiv hätte ich vermutet, dass der Weg über `.iteritems()` langsamer ist, da ich mehr Aufwand angenommen hatte, aber da haben mich die Zeitmessungen eines Besseren belehrt.

[kbr]

In Python lohnt sich stets ein Profiling, da die intuitive Einschätzung der Performance von Codekonstrukten oft in die Irre führt:

Code: Alles auswählen

In [1]: d = {'a':'a', 'b':'b', 'c':'c', 'd':'e', 'e':'f', 'f':'g'}

In [2]: %timeit sum(d[k]==k for k in d)
100000 loops, best of 3: 2.12 µs per loop

In [4]: %timeit sum(1 for k in d if k==d[k])
1000000 loops, best of 3: 1.75 µs per loop

In [5]: %timeit sum(1 for k, v in d.items() if k==v)
1000000 loops, best of 3: 1.92 µs per loop

Obiges lief mit Python 3.5 und es lässt sich erkennen: je weniger Werte der Generatorausdruck erzeugen muss, desto schneller läuft das ermitteln der Summe. Soweit ist das Ergebnis noch intuitiv. Weiter lässt sich annehmen, dass der Generator 'k, v in d.items()' langsamer läuft als 'k in d' da für jedes Element ein lookup in d erforderlich ist. Andererseits erfolgt dieses lookup bei 'k in d if k==d[k]' gleichfalls für jedes Element in d, was bei der Iteration über d.items() beim anschließenden Vergleich 'k==v' nicht mehr vorgenommen werden braucht. Womöglich hilft hier ein Blick in den erzeugten Bytecode, um das zu verstehen.

[Sirius3]

Ein schönes Beispiel, dass sich Profiling bei µs nicht lohnt, wenn die drei Lösungen quasi gleich sind. Hier ein Beispiel mit 10000 Dictionary-Einträgen:

Code: Alles auswählen

In [10]: %timeit sum(d[k]==k for k in d)
100 loops, best of 3: 15.7 ms per loop

In [11]: %timeit sum(1 for k in d if d[k]==k)
100 loops, best of 3: 13.9 ms per loop

In [12]: %timeit sum(1 for k, v in d.iteritems() if k==v)
100 loops, best of 3: 10.1 ms per loop

In erster Linie sollte man also so programmieren, wie es am lesbarsten ist.

[kbr]

Hier ein Beispiel mit 10000 Dictionary-Einträgen

Zugegeben: ich war zu faul, mal eben ein großes Dictionary aufzubauen. Bei nun verlängerten Laufzeiten zeigt dein Beispiel, dass die langsamste Lösung die langsamste bleibt (so wie es zu vermuten war), sich aber die Reihenfolge der beiden schnellen Lösungen umkehrt.

Wenn ich dies mit 10000 Einträgen nachvollziehe, ergibt sich das gleiche Verhalten.

Code: Alles auswählen

In [18]: %timeit sum(d[k]==k for k in d)
100 loops, best of 3: 2.38 ms per loop

In [19]: %timeit sum(1 for k in d if k==d[k])
1000 loops, best of 3: 1.65 ms per loop

In [20]: %timeit sum(1 for k,v in d.items() if k==v)
1000 loops, best of 3: 1.33 ms per loop

Die Frage aber, warum sich die beiden schnelle Lösungen in ihrem Laufzeitverhalten unterscheiden, bleibt offen.

In erster Linie sollte man also so programmieren, wie es am lesbarsten ist.

Das ist sicherlich richtig.
Da die Laufzeitunterschiede der beiden schnelle Lösungen nur gering sind, ist die Frage nach deren Ursache für mich auch eher von theoretischem Interesse.

[BlackJack]

Das ganze lässt jetzt auch total ausser Betracht was die Elemente eigentlich sind und damit wie teuer das ``==`` ist. In einem realen Anwendungsfall könnte das auch so teuer sein, dass der minimale Unterschied total irrelevant wird. Oder eine andere Interpreterversion macht etwas geringfügig anders, und schon stimmt dieses Ranking nicht mehr. Von timeit würde ich eher abraten und es so schreiben dass es lesbar ist. Profiling nur bei kompletten, echten Programmen mit echten oder zumindest sehr realitätsnahen Daten, und dann auch nur wenn die Programme zu langsam sind, oder man echt Langeweile hat.

[kbr]

@BlackJack: Klar, wenn ein komplexes Programm irgendwo klemmt, dann ist ein richtiges Profiling angebracht. Die Schnipsel oben sind da eher von akademischen Interesse. Das auch seine Berechtigung hat. Und dafür finde ich timeit gar nicht so schlecht.

[Goswin]

Das war zwar ein wenig mehr Antwort als von mir erwartet, aber ich danke allen und hoffe, dabei etwas zu lernen. Trotzdem konnte ich bisher bei dem folgenden Codeschnipsel noch nicht die eigentlich völlig überflüssige überflüssige Listenerstellung vermeiden (die Liste "nullberereich" gebrauche ich nie wieder); vermutlich gibt es da auch eine elegante Lösung, oder?

Code: Alles auswählen

nullbereich = [x for (x,ffx) in ff.items() if ffx==0]
for x in nullbereich: del(ff[x])

[BlackJack]

@Goswin: Ich würde da nichts löschen sondern ein neues Wörterbuch erzeugen. Seiteneffekte zu minimieren ist sowieso meistens eine gute Idee:

Code: Alles auswählen

ff = dict((x, ffx) for x, ffx in ff.iteritems() if ffx != 0)

(Beziehungsweise ``ff.items()`` wenn man Python 3 verwendet.)

[Hyperion]

@BlackJack: Magst Du keine Dict-Comprehensions?

[Goswin]

@BlackJack:
AttributeError: 'collections.defaultdict' object has no attribute 'iteritems'

Natürlich kann ich das defaultdict auch durch ein einfaches dict ersetzen, aber das macht den gesamten Code um einiges undurchsichtiger . Gewinne ich dafür an Geschwindigkeit?

[BlackJack]

@Hyperion: Nee, neumodisches überflüssiges Zeug (und funktioniert nicht in Python <=2.6 ).

@Goswin: Na dann `items()` wenn Du Python 3 verwendest. Steht doch auch in meinem letzten Beitrag.

Bei einem `defaultdict` würde es vom Kontext abhängen was ich da machen würde, also ob ich das verändere oder ein neues erstelle um Nebeneffekte zu minimieren.

Was die Geschwindigkeit angeht: Darüber würde ich mir keine Gedanken machen solange es sich rein um konstante Faktoren handelt und das gesamte Programm nicht messbar zu langsam ist. Das hatten wir ja schon bei der Diskussion über `timeit`. Solche Mikrooptimierungen oder sich alleine Gedanken darüber zu machen kosten oft mehr Zeit als sie an Laufzeit wieder reinbringen. Auf der anderen Seite kann die Fehlersuche eines Nebeneffektes auch mehr Zeit (und Nerven) kosten als man beim verändern einer existierenden Datenstruktur gespart hat/hätte.

[Goswin]

@Blackjack:
Ja, jetzt funktioniert es, vielen Dank!

Was die Geschwindigkeit angeht: Mein Programm läuft seit 3_Tagen im Hintergrund, und wird vermutlich noch 3_weitere Tage brauchen, bis es fertig ist. Aber da ich 4_Prozessoren habe, teste ich währenddessen Alternativversionen, um den Code schneller zu machen.

[cofi]

Bei der Groessenordnung ist das Problem wahrscheinlich ein strukturelles. Oder du verarbeitest einfach so viele Daten
Mit Bestimmtheit kann man aber sagen, dass du mit solchen Tricks eher eine Veraenderung im Stunden statt Tagebereich erreichst. Wenn ueberhaupt.

[BlackJack]

@Goswin: Das ist dann kein Fall für `timeit` sondern tatsächlich einer für Profiler die sich mal das gesamte Programm anschauen um erst mal die Stellen zu ermitteln bei denen der grösste Gewinn erwartbar ist, bevor man da viel Zeit in Mikrooptimierungen versenkt die am Ende vielleicht nicht einmal einstellige Prozentwerte in der Geschwindigkeitssteigerung bringen.

Und so ganz grundsätzlich würde ich bei Tagen auch erst einmal die Algorithmen und Datenstrukturen auf den Prüfstand stellen. Und dann ob sich da etwas parallelisieren lässt.