Geschwindigkeitsproblem bei nem Algo

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 2. März 2005, 20:53

DasPinsch hat geschrieben: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.

DasPinsch hat geschrieben: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.

DasPinsch hat geschrieben: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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasPinsch

Beitragvon DasPinsch » Mittwoch 2. März 2005, 21:06

Stimmt, dein Code ist deutlich lesbarer, würde mich aber auch nicht wagen sowas in C++ zu schreiben :P
hatte zuerst eine übersichtliche Funktion, hab diese dann aber versucht noch weiter zu optimieren und gleichzeitig alle variablennamen gekürzt :oops:
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 ;)
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 2. März 2005, 21:31

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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Donnerstag 3. März 2005, 07:03

Leonidas hat geschrieben: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)
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 3. März 2005, 13:35

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()
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Beitragvon BlackJack » Freitag 4. März 2005, 00:47

DasPinsch hat geschrieben: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
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Freitag 4. März 2005, 11:53

Leonidas hat geschrieben:
DasPinsch hat geschrieben: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.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Freitag 4. März 2005, 13:25

Milan hat geschrieben: 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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]