Geschwindigkeitsproblem bei nem Algo

[Leonidas]

Ehrlich gesagt sehe ich nicht wirklich den Unterschied (natürlich arbeitest du nach einem anderen Verfahren und hast direkt mehrere Funktionen mit einigem drumherum, aber die Funktionen als solche sind doch vom Stil nicht sehr anders?!)

Mein Code ist lesbarer Davon abgesehen würde ich den inzwischen mit yield machen.

Zwei Sache ist mir noch aufgefallen, du schreibst immer:
x = x + 1
anstatt
x += 1, ist das 2. nicht schneller?

Sie sind gleich schnell, denn die Schreibweisen sind äquivalent. Aber ältere Pythonversionen kennen kein "Augmented Assign". Das wäre noch zu ändern, ich werde mal die aktuelle Version in die Codesnippets posten.

Zudem benutzt du bei Zaheln so weit ich das gesehen habe den "is" Operator anstatt dem "=="! Ist "is" schneller?

Nein, das war ein Fehler meinserseits (der Code an sich ist älter als 1. 2004), wie weiter im Thread geschreiben wird.

[DasPinsch]

Stimmt, dein Code ist deutlich lesbarer, würde mich aber auch nicht wagen sowas in C++ zu schreiben
hatte zuerst eine übersichtliche Funktion, hab diese dann aber versucht noch weiter zu optimieren und gleichzeitig alle variablennamen gekürzt
gleich noch ne Frage:
ist
for i in xrange(1000):
bla

schneller oder langsamer als
i = 0
while i < 1000:
bla
i += 1

?
irgendwie habe ich Angst, dass das Erstellen einer Liste viel Zeit in Anspruch nehmen könnte

[Leonidas]

Wenn es dir um absolute Performance geht, muss du in python Module auslagern.
Guck dir mal das timeit Modul an, damit kannst du die Geschwindigkeit selbst herusfinden.

Ich würde die for Schleife nehmen, nicht weil sie schneller ist (das vermutlich nicht), sondern weil der Code eleganter ist, und darauf kommt es in Python oft an.

Zur Optimierung hier mal ein interessanter Text. Pytho sieht man es nicht an, wie lange etwas dauert, man muss es einfach testen.

[jens]

Ich würde die for Schleife nehmen, nicht weil sie schneller ist (das vermutlich nicht)...

Nep! While ist langsamer:

Code: Alles auswählen

import time

loops = 10000000

start = time.time()
for i in xrange( loops ): pass
end = time.time()

time1 = end - start
print "for: %.3fs" % time1

start = time.time()
i = 0
while i < loops: i += 1
end = time.time()

time2 = end-start
print "while: %.3fs" % time2

print "diff: %.3fs" % (time2 - time1)

Ergebnis:

Code: Alles auswählen

for: 2.093s
while: 4.063s
diff: 1.970s

Aber das war doch auch zu erwarten... Bei der while schleife wird einfach mehr gemacht, erst ein Vergleich, dann manuell die Variable i um eins hochgesetzt... (Das liegt auch nicht daran, das in den Schleifen nicht's gemacht wird... Wenn man bei beiden ein sinnloses a=str(i) macht, bleibt der Unterschied)

[Leonidas]

Hast recht, hier nochmal der Benchmark mit dem dediziiertem timeit Modul:

Code: Alles auswählen

#!/usr/bin/env python
# -*- encoding: latin-1 -*-

whilecode = """i = 0
while i < 10:
    i += 1
"""

forcode = """for i in xrange(10):
    pass
"""

def testit(times=10000):
    from timeit import Timer
    
    t = Timer(whilecode)
    whiletook = t.timeit(number=times)
    t = Timer(forcode)
    fortook = t.timeit(number=times)
    print "While vs. For: %i loops" % times
    print
    print "%.3f sec/all \tWhile" % whiletook
    print "%.3f sec/all \tFor" % fortook
    print "%.2f usec/pass While" % (1000000 * (whiletook/times))
    print "%.2f usec/pass For" % (1000000 * (fortook/times))

if __name__ == '__main__':
    testit()

[BlackJack]

gleich noch ne Frage:
ist
for i in xrange(1000):
bla

schneller oder langsamer als
i = 0
while i < 1000:
bla
i += 1

?
irgendwie habe ich Angst, dass das Erstellen einer Liste viel Zeit in Anspruch nehmen könnte

Die Funktion `xrange()` erstellt im Gegensatz zu `range()` keine Liste sondern ein Objekt, das sich nur so verhält als wäre es eine Sequenz. Der Speicherverbrauch für `xrange(10)` ist der gleiche wie der für `xrange(100000)`.

An Deinem Primzahlentest finde ich "unpythonic", das er Schritt für Schritt dem Computer erklärt was er machen soll, aber für einen Menschen nicht "lesbar" ist. Man muss auch erstmal schauen was getan wird.

Schöner finde ich zum Beispiel dieses Rezept: http://aspn.activestate.com/ASPN/Cookbo ... ipe/117119

Ich habe gerade ein wenig nach A* gesucht und es scheint den normalen Dijkstra Algorithmus um eine Heuristik zu erweitern. Ich würde es erstmal mit dem normalen Dijkstra probieren und schauen ob der von der Geschwindigkeit her nicht ausreicht. Die Knotenmenge U verwaltet man am besten in einer Heap-Queue. Python liefert netterweise ein entprechendes Modul: 'heapq'. Das ist wesentlich schneller als Listen + sortieren.

[Milan]

Zwei Sache ist mir noch aufgefallen, du schreibst immer:
x = x + 1
anstatt
x += 1, ist das 2. nicht schneller?

Sie sind gleich schnell, denn die Schreibweisen sind äquivalent.

HI. Das etwas äquivalent ist heißt noch lange nicht das es gleich schnell ist. x+=1 ist um einiges schneller als x=x+1, das hängt damit zusammen das im ersten Fall schon bekannt ist wohin das Ergebnis gespeichert werden soll und wo der Ausgangswert steht. Im 2. Fall wird erst gesagt, dass er nach x speichern soll und dann muss er rechts vom Gleichheitszeichen nochmal das x ausm speicher rauskramen.

[Leonidas]

Das etwas äquivalent ist heißt noch lange nicht das es gleich schnell ist. x+=1 ist um einiges schneller als x=x+1, das hängt damit zusammen das im ersten Fall schon bekannt ist wohin das Ergebnis gespeichert werden soll und wo der Ausgangswert steht. Im 2. Fall wird erst gesagt, dass er nach x speichern soll und dann muss er rechts vom Gleichheitszeichen nochmal das x ausm speicher rauskramen.

Ja, hast recht, denn bei x = x + 1 wird zweimal nach x gesucht.. na, ich habe es mal in meinem Benchmark gefixt.