Maximum recursion depth

[MarcelF6]

Hallo miteinander,

ich bin gerade dabei, die Subsequenz von drei Strings zu berechnen, mit folgendem Code:

Code: Alles auswählen

def subseq(xs, ys, zs):

    if xs and ys and zs:
        xb = xs[-1]
        yb = ys[-1]
        zb = zs[-1]
        if xs[-1] == ys[-1]:
            if xs[-1] == zs[-1]:
                return subseq(xb, yb, zb) + [xs[-1]]
        else:
            return max(subseq(xs, yb, zb), subseq(xb, ys, zb), subseq(xb, yb, zs), key = len)
    else:
        return []

Allerdings habe ich das Problem, dass das Rekursionslimit erreicht wird. Somit stellt sich die Frage: Ist etwas am Code nicht so toll oder wie kann ich dieses Limit "umgehen"?

Danke für jeglichen Hinweis.

[Dav1d]

Du kannst es höher setzen mit sys.setrecursionlimit

[MarcelF6]

Danke für die schnelle Antwort!
Leider muss es aber doch einen Fehler im Code haben, denn die Erhöhung des Rekursionslimits bringt mir bei 100000 Rekursionen einen Speicherzugriffsfehler. Obwohl ich niemals 10000 Rekursionen erwarte, wird auch da eine Fehlermeldung geworfen, dass das Rekursionslimit erreicht sei.

Sieht jemand, wo das Problem steckt?

[snafu]

Vielleicht sagst du mal ein bißchen mehr zur Aufgabenstellung: Meint "Subsequenz von 3 Strings", dass du das erste Auftreten eine Zeichenfolge, die in allen 3 Strings an der selben Stelle vorkommt, zurückgeben willst?

Falls ja, dann kann man das auch ohne Rekursion lösen.

[jerch]

@MarcelF6:
Deine Funktion erreicht niemals den äußeren else-Zweig, wenn nicht schon zu Anfang ein String leer ist (Vgl. hierzu s[-1] und s[-1][-1]), während alle anderen exitpoints rekurrieren.

Übrigens ist dies mit mit der Argumentenmodifikation zur Laufzeit (xs zu xb) und 4 möglichen Rekursionsaufrufen ein sehr schönes Bsp, wie man unverständlichen und unwartbaren Code mit Rekursionen bauen kann

[MarcelF6]

@snafu: nein, gemeint sind einfach gemeinsame Buchstaben. Beispiel mit 2 strings: "hallo", "donnerstag" --> output: "o", "a".
@jerch: danke für den Hinweis. Bin das Problem gerade am Überprüfen und testen...

[/me]

@snafu: nein, gemeint sind einfach gemeinsame Buchstaben. Beispiel mit 2 strings: "hallo", "donnerstag" --> output: "o", "a".

So etwas?
(Die & im Code bitte gedanklich durch ein einfaches & ersetzen. Das ist ein Formatierungsfehler.)

Code: Alles auswählen

>>> values = ['hallo', 'donnerstag', 'chaos']
>>> data = map(set, values)
>>> print data[0] & data[1] & data[2]
set(['a', 'o'])

Die Formatierungsprobleme im Forum könnte man mit einem etwas flexibleren Ansatz umgehen

Code: Alles auswählen

print data[0].intersection(*data[1:])

[MarcelF6]

Genau. Nur sollte ich 'set' halt ausschreiben, dh so ähnlich wie ichs probiert habe als Funktion implementieren. Für zwei Strings zB habe ich eine funktionierende Funktion. Somit könnte ich also auch nur 'reduce' beim Funktionsaufruf verwenden, um mehrere strings zu bearbeiten. Aber so wird's kaum (nicht) gedacht sein...schliesslich sollte dann auch der Funktionsaufruf subseq(str1, str2, str3) sein.

[MarcelF6]

@jerch: Ich habe den Code mittlerweile angepasst und angepasst, aber nicht so hingekriegt, dass er macht, was ich gerne hätte. Das Problem liegt ja wahrscheinlich hier:

Code: Alles auswählen

if xs[-1] == ys[-1]:
            if xs[-1] == zs[-1]:

Aber wieso werden hier so viele Rekursionen gemacht?
Du hast noch auf s[-1][-1] hingewiesen - aber das würde hier ja keinen Unterschied machen...oder wie hast du das gemeint?

[EyDu]

Baue doch einfach mal ein print-Statement ein, welches dir die Variablen ausgibt. Dann ist dein Fehler offensichtlich. jerch hat es ganz am Anfang ja schon gesagt.

[MarcelF6]

Ok, ich habe mittlerweile einige Fehler entdeckt.
Aber so kanns noch nicht stimmen, denn die Funktion findet nie einen gleichen Buchstaben; auch wenns da welche hätte. Woran könnte das liegen?

[EyDu]

Du hast gleich zwei ordentliche Fehler eingebaut: zum einen ist das max nicht korrekt (da du unter Umständen neue Buchstaben ignorierst) und die Rekursionen in max sind auch falsch. Du veränderst nicht nur einen Parameter sondern immer zwei.

Wie schon geschrieben: mit Ausgabe der Zwischenschritte und einem Beispiel mit zwei Buchstaben ist das Problem offensichtlich.

Sebastian

[MarcelF6]

Danke für die Hinweise. Also das mit den Rekursionen kann ich nachvollziehen. Wieso aber ist max falsch? Bzw. ich verstehe nicht ganz, was denn dort anderes hinkommen soll als das Maximum.. Danke für die Aufklärung

[EyDu]

Lass die die Parameter von max doch mal für den Fall subseq("ah", "ah", "ha") ausgeben.

[MarcelF6]

Ah okey...ich seh das Problem. Bleibt aber die Frage, was anstelle von max hinkommen soll. Ich weiss ja nicht von Anfang an, welche der drei die "korrekte" Rekursion ist...

[MarcelF6]

Mittlerweile habe ich den Code ab dem if-Statement mit elif-Statements aufgefüllt.

max hab ich nun mal gelassen, weil ich der Meinung bin, dass es doch korrekt ist (für meinen Code).
Nun erhalte ich auch eine Ausgabe, die eigentlich alle korrekten Subsequenzen enthält. Leider aber auch solche, die keine sind. Das kommt daher, dass ich immer zwei miteinander vergleiche. Da mir aber noch keine Lösung eingefallen ist, wie ich das codemässig berücksichtigen soll, dass zuerst zwei verglichen werden sollen und dann das Ergebnis mit dem dritten String, stelle ich die Frage hier.

Ursprünglich habe ich einfach unter die elif-Statements noch einmal ein if-Statement gesetzt, also z.B.:

Code: Alles auswählen

elif xs[-1] == ys[-1]:
        if xs[-1] == zs[-1]:
            return subseq(xb, yb, zb) + [xs[-1]]

...aber mit dieser Variante kam ich zu keinem Ergebnis.

[jerch]

Die elif-Kaskade bringt nichts, dass Du da auch Dubletten findest ist doch klar, scliesslich testest Du auch auf diese.

Schau Dir lieber nochmal das max an, dort werden nämlich schonmal gefundene Lösungen wieder verworfen.

[jerch]

Vllt. fällt Dir das Problem mit dem max auf, wenn man Positionsangaben hinzufügt:

Code: Alles auswählen

def seq(a,b,c):
    len_x = len(a)
    len_y = len(b)
    len_z = len(c)
    f = lambda x,y,z: [] if not all((x,y,z)) else f(x[1:],y,z)+f(x,y[1:],z)+f(x,y,z[1:])\
        if not (x[0]==y[0]==z[0]) else (f(x[1:],y[1:],z[1:])+
        [(x[0], len_x-len(x),len_y-len(y),len_z-len(z))])
    return list(set(f(a,b,c)))

NB: Mit lambda bekommt man immer so schöne Einzeiler

[MarcelF6]

YES, finally
Vielen Dank für die Geduld und - vor allem - für das letzte Beispiel. Eigentlich hat mir erst das richtig die Augen geöffnet. ...der Code war eigentlich ganz ok - wenn ich dann gefundene Lösung nicht ignoriert (überschrieben) hätte...
Danke nochmals vielmals

[jerch]

@MarcelF6:
Ich weiss nicht, was eure Aufgabenstellung/Zielsetzung war, allerdings ist das Problem sehr ungünstig gelöst, da Deine Rekursionen unnötigerweise den Entscheidungsbaum mehrfach ablaufen (daher kommen auch die Dopplungen, die Du wieder filtern musst).

Edit:
Wenn es unbedingt Rekursion sein soll, hier mal ein anderer Vorschlag:

Code: Alles auswählen

def seq(*args):
    if len(args) == 1:
        return args[0]
    return seq(filter(lambda x: x in args[1], args[0]), *args[2:])

Die Funktion nimmt eine beliebige Anzahl von Strings/Iterables auf und konsumiert diese per Rekursion. Die Laufzeit sollte wesentlich besser sein als in Deinem Bsp.

Allerdings ist für diesen einfachen Anwendungsfall der Weg über sets, wie /me es gezeigt hat, allen eigenen Versuchen vorzuziehen. Sollte die Positionsangabe eine Rolle spielen, würde ich eher über ein Alphabetwörterbuch gehen:

Code: Alles auswählen

def seq(*args, **kwargs):
    hits = kwargs.get('hits')
    if not hits:
        hits = len(args)
    temp = {}
    for i,s in enumerate(args):
        for j,c in enumerate(s):
            item = temp.setdefault(c, [[] for _ in xrange(len(args))])
            item[i].append(j)
    return filter(lambda kv: len(filter(bool, kv[1]))==hits, temp.iteritems())

Über hits kann man dann auch andere Häufigkeiten abfragen.