Vorteil eines rekursiven Suchalgorithmus

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.
Antworten
Benutzeravatar
pixewakb
User
Beiträge: 1408
Registriert: Sonntag 24. April 2011, 19:43

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

Code: Alles auswählen

print(suche(nummernliste, "0201"))
Zap
User
Beiträge: 533
Registriert: Freitag 13. Oktober 2006, 10:56

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.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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. :o

Der Autor der Funktion scheint übrigens `str.startswith()` noch nicht zu kennen...
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.
mutetella
User
Beiträge: 1695
Registriert: Donnerstag 5. März 2009, 17:10
Kontaktdaten:

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
Entspanne dich und wisse, dass es Zeit für alles gibt. (YogiTea Teebeutel Weisheit ;-) )
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

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.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

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
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

@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.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

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
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

@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.
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

@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.
Das Leben ist wie ein Tennisball.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Selbst bei einem Rekursionslimit von 1000 kann ich damit immer noch ein Element unter 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 Elementen finden :)

Stefan
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Dann habe ich die "Macht" der binären Suche wohl deutlich unterschätzt. :o
Antworten