Seite 1 von 1
Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 03:17
von pixewakb
Ich schaue aktuell ins Lehrbuch von Michael Weigend.
Auf Seite 186 und 187 erklärt er, wie ein rekursiver Suchalgorithmus aussehen kann. Ich verstehe dort nicht, worin der Vorteil eines solchen Verfahrens gegenüber einer Variante besteht, die einfach prüft, ob jedes Element einer Liste zur Vorwahl passt.
Ich habe den Quellcode etwas angepasst, um eine Zählschleife zu implementieren.
Code: Alles auswählen
zahl = 0
def suche(num, vorwahl):
global zahl
zahl += 1
print(num, zahl)
if len(num) == 1:
if num[0][:len(vorwahl)] == vorwahl:
return num
else:
return []
else:
return suche(num[:len(num)//2], vorwahl)+\
suche(num[len(num)//2:], vorwahl)
nummernliste = ['0223 788834',
'0201 566722',
'0224 66898',
'0201 899933',
'0208 33987']
Aufruf in der Konsole mittels
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 05:06
von Zap
Ein solcher Suchalgorithmus (Binäre Suche) ist nur dann von Vorteil wenn die Liste sortiert ist. Bei diesem Beispiel liegt keine Sortierung vor und somit sehe ich hier keinen Vorteil.
Generell würde ich in Python ehr selten eigene Suchalgorithmen implementieren. Listen und andere Container haben methoden on board für solche Zwecke. Aber das nur als pragmatischer Hinweis. Sich mit der Theorie auseinanderzusetzen ist auf keinen Fall falsch.
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 05:25
von snafu
Zap hat geschrieben:Ein solcher Suchalgorithmus (Binäre Suche) ist nur dann von Vorteil wenn die Liste sortiert ist. Bei diesem Beispiel liegt keine Sortierung vor und somit sehe ich hier keinen Vorteil.
Und was würde das bei einer vorliegenden Sortierung bringen? Es muss doch so oder so jedes Element einzeln durchlaufen werden.
Der Autor der Funktion scheint übrigens `str.startswith()` noch nicht zu kennen...
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 09:08
von BlackJack
Ergänzend zu Zap: So eine Binäre Suche muss man tatsächlich nicht selber implementieren: Die kommt schon mit der Standardbibliothek im `bisect`-Modul.
@snafu: Es wird bei Binärer Suche immer das Element in der Mitte des Intervalls angeschaut. Und je nach dem ob dass dann grösser oder kleiner ist, wird in der ersten oder in der zweiten Hälfte nach dem gleichen Verfahren weiter gesucht. Wenn das Element in der Mitte einer sortierten Liste kleiner als das gesuchte ist, dann weiss man ja, dass alle davor noch kleiner sind, und somit gar nicht erst betrachtet werden müssen.
Der Quelltext passt dazu allerdings nicht ganz.
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 11:58
von mutetella
Wenn man das Beispiel mit print's bestückt, erkennt man vielleicht ein wenig besser, was da vor sich geht:
Code: Alles auswählen
def suche(num, vorwahl):
if not isinstance(num, Num):
num = Num(num, name='num.')
if len(num.num) == 1:
if num.num[0].startswith(vorwahl):
print '{0:<12}trifft.'.format(num.name)
return num.num
else:
print '{0:<12}trifft nicht.'.format(num.name)
return []
else:
num_back = Num(num=num.back(), name=num.name+'A')
num_front = Num(num=num.front(), name=num.name+'B')
print '''
{0.name:<12}{0.num} wird geteilt in
{1.name:<12}{1.num} und
{2.name:<12}{2.num}'''.format(num, num_back, num_front)
return suche(num_back, vorwahl) + suche(num_front, vorwahl)
class Num(object):
def __init__(self, num, name):
self.num = num
self.name = name
def front(self):
return self.num[:len(self.num)//2]
def back(self):
return self.num[len(self.num)//2:]
mutetella
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 17:43
von sma
Das Beispiel macht wie gezeigt wenig Sinn. Wie bereits mehrfach erwähnt, würde eine binäre Suche nur auf einer sortierten Liste funktionieren. Das ganze ist aber auch ein anderer Algorithmus, da nicht nur ein Ergebnis, sondern alle Telefonnummern mit einer bestimmten Vorwahl gefunden werden.
Nutzt man (End-)Rekursion als Schleifenkonstrukt, sähe das Beispiel ungefähr so aus:
Code: Alles auswählen
def suche(num, vorwahl):
def suche_itr(num, erg):
if num:
if num[0].startswith(vorwahl):
return suche_itr(num[1:], erg + num[:1])
else:
return suche_itr(num[1:], erg)
else:
return erg
return suche_itr(num, [])
Allerdings halte ich es für wesentlich einfacher, das ganze mit einer for-Schleife zu realisieren:
Code: Alles auswählen
def suche(num, vorwahl):
erg = []
for n in num:
if n.startswith(vorwahl):
erg.append(n)
return erg
Und wenn man das verstanden hat, kann man das zu einer List-Comprehension verkürzen:
Code: Alles auswählen
def suche(num, vorwahl):
return [n for n in num if n.startswith(vorwahl)]
Für Rekursion ist das gezeigte Programm jedenfalls ein denkbar dämliches Beispiel.
Stefan
PS: Eine Zählschleife halte ich für den falschen Begriff, wenn, dann ist das ein Rekursionszähler oder meinetwegen ein Schleifenzähler, aber eben keine Schleife, die zählt, sondern ein Zähler, der die Durchläufe registriert.
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 17:48
von snafu
Ich denke auch, die LC wird hier am sinnvollsten sein. Bekanntlich sind in Python Funktionsaufrufe recht teuer, so dass man sich Rekursion im Sinne von (vermeintlicher) Optimierung wirklich zweimal überlegen sollte. Davon abgesehen ist eine LC natürlich auch eleganter und lesbarer.
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 17:59
von sma
snafu hat geschrieben:Rekursion im Sinne von (vermeintlicher) Optimierung wirklich zweimal überlegen sollte
Rekursion optimiert in erster Linie den Algorithmus (im Sinne von macht ihn einfacher verständlich) und nicht die Laufzeit. Ersteres ist aber in der Regel wichtiger, gerade wenn fremde Programme (d.h. die eigenen nach einigen Monaten oder Jahren) verstehen muss/will. Auf die Laufzeit zu schielen, ist meist eine vorschnelle Optimierung und ein Urübel.
Stefan
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 18:07
von snafu
@sma: Hier dient der rekursive Ansatz aber offenbar auschließlich der Laufzeit-Optimierung und nicht der Verständlichkeit. Daher ist die LC als Ansatz deutlich besser. Das wollte ich damit sagen.
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Freitag 5. August 2011, 19:11
von sma
snafu hat geschrieben:@sma: Hier dient der rekursive Ansatz aber offenbar auschließlich der Laufzeit-Optimierung.
In dem ursprünglichen Beispiel dient die Rekursion keinem Zweck bzw. nur der Verschleierung des Algorithmus. Man sucht mal links mal rechts nach passenden Nummern und addiert die Ergebnisse auf.
Stefan
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Samstag 6. August 2011, 06:48
von snafu
@sma: Wir kamen von dem ursprünglichen Snippet auf das Thema "binäre Suchalgorithmen". Ich vermute auch, dass die Idee hinter dem Snippet ebenfalls die Implementierung eine Art binärer Suche war. Daraufhin habe ich gesagt, dass man solche Laufzeit-Optimierungen, sofern sie viele Funktionsaufrufe beinhalten, durchaus hinsichtlich des Aspekts prüfen sollte, dass Rekursion nicht unbedingt etwas ist, was von Python optimal unterstützt wird. Sprich: Man kann sich neben schlechter Lesbarkeit auch am Ende die Performance damit kaputt machen.
Andererseits kann es sich, je nach vorhandenen Daten, vielleicht doch lohnen, wenn viele gleiche Elemente übersprungen werden. Das ist aber eine Sache, bei der man den tatsächlichen Unterschied der Laufzeit erstmal testen müsste. Wie du schon sagtest, vorschnelle Optimierungen auf Kosten der Lesbarkeit - und damit auch der Wartbarkeit - sind grundsätzlich eine schlechte Idee.
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Samstag 6. August 2011, 07:21
von EyDu
@snauf: Binäre Suche würde ich, wenn man viele Anfragen an eine Datenmenge hat welche sortierbar ist, nicht als Laufzeitoptimierung beschreiben, da sie für diesen Bereich Standard ist. Das Rekursionslimit und die wenigen Funktionsaufrufe fallen hier überhaupt nicht ins Gewicht, da die Menge der zu untersuchenden Daten sich bei jedem Iterationsschritt halbiert. Als Regel würde ich sagen, dass Algorithmen immer in der minimalen Komplexität, solange diese auch noch praktikabel ist, implementiert werden sollten.
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Samstag 6. August 2011, 07:54
von sma
Selbst bei einem Rekursionslimit von 1000 kann ich damit immer noch ein Element unter 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 Elementen finden
Stefan
Re: Vorteil eines rekursiven Suchalgorithmus
Verfasst: Samstag 6. August 2011, 08:14
von snafu
Dann habe ich die "Macht" der binären Suche wohl deutlich unterschätzt.
