Seite 2 von 2
Verfasst: Sonntag 18. Februar 2007, 13:01
von nkoehring
@autos: ich habe Python auch nur durch OnlineTutorials, durch dieses Forum und durch reine Neugierde gelernt.
Python bringt dafuer auch alles mit. Die Grundlagen findest du im Tutorial auf python.org, als Spielwiese hast du den Interpreter, der direkt ausfuehrbar ist, und Fragen zu einzelnen Details hast du beim Interpreter eine help()-Funktion. Was will man mehr??
Verfasst: Sonntag 18. Februar 2007, 14:15
von BlackJack
@Groucho: Wenn Du die Liste sowieso immer durchreichst, dann hast Du eine iterative Lösung geschrieben, nur undurchschaubarer, langsamer und komplizierter als wenn man es gleich mit einer Schleife geschrieben hätte.
Rekursive Lösungen bieten sich immer an, wenn man eine grosses Problem in kleinere gleichartige Probleme zerlegen kann, die unabhängig voneinander gelöst werden und dann wieder zu einer Gesamtlösung zusammengefügt werden können. Hier braucht die Lösung jedes Teilproblems aber die Lösung vom vorhergehenden, d.h. das Lösen der einzelnen Teilprobleme geschieht wiederholt nacheinander. Also eigentlich in einer Schleife.
Verfasst: Sonntag 18. Februar 2007, 17:56
von Groucho
@BlackJack: Da hast Du natürlich recht: Ich dachte zuerst, ich gewinne etwas durch die Rekursion, weil ich die zerlege-Funktion nach dem Aufinden eines Faktors mit Parameter
zahl/faktor statt mit
zahl aufrufen kann und die Prüfung dann nur bis zu
sqrt(zahl/faktor) statt bis
sqrt(zahl) laufen muss.
Das kann ich aber genauso in der iterativen Variante berücksichtigen und die ist dann natürlich schneller als die rekursive.

Verfasst: Montag 19. Februar 2007, 16:47
von Groucho
Nochmal zum Thema rekursive vs. iterative Lösung:
Das Grundproblem ist meines Erachtens rekursiv: Hat man nämlich einen
faktor von
zahl gefunden, so ist [Zerlegung von zahl] = [faktor] + [Zerlegung von zahl/faktor]. Für
zahl/faktor braucht man auch nur noch die Teiler ab
factor prüfen, die kleineren sind ja schon erledigt.
Das Problem ist also auf ein gleichartiges einfacheres Problem reduziert, wobei die Rekursion terminiert, wenn die noch zu prüfende Zahl eine Primzahl ist.
Hier eine echte rekursive Lösung (ohne Durchreichung der Ergebnisliste

):
Code: Alles auswählen
from math import sqrt
def zerlege_rekursiv(zahl,start_faktor=2):
if start_faktor <= sqrt(zahl): # wenn noch nicht am Ende
if start_faktor == 2: # zuerst auf Faktoren 2 prüfen
if zahl%2 == 0:
# Faktoren: [2] + [Faktoren von zahl/2]
return ([2]+zerlege_rekursiv(zahl/2,2))
else:
start_faktor = 3
# ungerade Zahlen von start_faktor bis sqrt(zahl) kommen
# Teiler in Frage
for faktor in xrange(start_faktor, int(sqrt(zahl))+1,2):
if zahl % faktor == 0:
# Faktoren: [faktor] + [Faktoren von zahl/faktor]
# beginne dort bei faktor, kleinere Teiler schon geprüft
return ([faktor] + zerlege_rekursiv(zahl/faktor,faktor))
# verbleibende zahl ist prim -> selbst in Teilerliste aufnehmen
return [zahl]
und hier die entsprechende iterative Lösung:
Code: Alles auswählen
def zerlege_iterativ(zahl):
faktor_liste = []
while zahl % 2 == 0: # zuerst auf Faktoren 2 prüfen
zahl /= 2
faktor_liste.append(2)
if zahl>1: # wenn nicht nicht am Ende
faktor = 3 # ungerade Zahlen ab 3 als Teiler prüfen
upperlimit = sqrt(zahl) # Obergrenze ist sqrt(zahl)
while faktor <= upperlimit:
while zahl % faktor == 0: # wenn Teiler gefunden
faktor_liste.append(faktor)
zahl/= faktor # nur noch zahl/faktor prüfen
upperlimit = sqrt(zahl) # und neue Obergrenze beachten
faktor += 2
if zahl>1: # verbleibende zahl ist prim -> selbst aufnehmen
faktor_liste.append(zahl)
return (faktor_liste)
Die iterative Lösung ist etwa 10% schneller, die (neue) rekursive aber leichter lesbar.
Code: Alles auswählen
from benchmark import Benchmark
def fiter(lower,upper):
for i in xrange(lower,upper):
zerlege_iterativ(i)
def frek(lower,upper):
for i in xrange(lower,upper):
zerlege_rekursiv(i)
lower = 20000
upper = 60000
bench = Benchmark()
bench.add_function(fiter, "iterativ", lower,upper)
bench.add_function(frek, "rekursiv", lower,upper)
bench.run()
bench.print_ranking()
benchmark.py aus
http://paste.pocoo.org/show/83/ siehe
http://www.python-forum.de/viewtopic.php?p=58861#58861
mit dem Ergebnis:
[Die Laufzeit wird ermittelt]
run: fiter - iterativ OK (1.19sec.)
run: frek - rekursiv OK (1.30sec.)
[Ranking wird erzeugt]
Ranking wurde erzeugt.
-------------------------------------------------------------------------------
Funktion: frek - rekursiv ist am langsamsten; Zeit: 1.301108 sec
Funktion: fiter - iterativ ist um 9.22% schneller; Zeit: 1.191261 sec
-------------------------------------------------------------------------------
Verfasst: Montag 19. Februar 2007, 17:35
von BlackJack
Ich finde beide gleich (un)lesbar. Die rekursive Funktion hat den Nachteil, das Funktionsaufrufe teurer sind als Schleifen, das es ein Rekursionslimit gibt und das nach der Rückkehr von jedem rekursiven Aufruf die Liste einmal kopiert wird, nur um ein Element hinzuzufügen.