Das deutsche Python-Forum

Hallo,

ich bin über ein komisches Verhalten gestolpert, was ich mir nicht so recht erklären kann.
Definiere ich einen Memoization-Dekorator, einmal als Klasse und einmal als Funktion, für eine rekursive Funktion, habe ich verschiedene maximale Rekursionstiefen bei der Ausführung. Mit der Standard Rekursionstiefe von 1000, bricht der Interpreter beim Klassendekorator bei 333 ab und beim Funktionsdekorator bei 500.
Es verwirrt mich ein Wenig, da die beiden Implementierungen an sich identisch sind.
Rein theoretisch müssten ja bei der Klasse mehr Rekursionsschritte ausgeführt werden, als bei der Funktion, damit so ein Verhalten ensteht. Aber warum führt die Klasse mehr Schritte aus? Vielleicht hat jemand hier eine Idee und kann mir helfen?

Code: Alles auswählen

class Memoize:
    def __init__(self, func):
        self.func = func
        self.memo = {}
    def __call__(self, x):
        if x not in self.memo:
            self.memo[x] = self.func(x)
        return self.memo[x]

@Memoize
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

"RecursionError: maximum recursion depth exceeded in comparison" <- bei 333

Code: Alles auswählen

def memoize(func):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = func(x)
        return memo[x]
    return helper

@memoize
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

"RecursionError: maximum recursion depth exceeded in comparison" <- bei 500

So etwas wie ``obj.attribute`` hat einen Aufruf zur Folge um das Attribut vom Objekt abzufragen.

Ok, hätte jetzt nicht gedacht, dass sich das auf die Rekurionsschritte auswirkt.

Verstehe ich auch nicht. Bei den Rekursionsaufrufen ist er doch immer nur in einer bestimmten Funktion und nicht in mehreren gleichzeitig. Wie soll der Zwischenschritt mit __getattribute__() damit Auswirkungen auf die Rekursionstiefe haben? Also außer dass sie kurz um eins erhöht wird?

@_Mala_Fide_: Wie bist Du denn auf die Zahlen gekommen? Welche Zahlen wann funktionieren hängt auch von der ”Historie” ab, also welche vorher berechnet wurden und was deshalb schon im Cache vorhanden ist oder nicht. Bei der Klasse funktioniert bei mir nicht mal ``fib(200)`` wenn nicht beispielsweise ``fib(100)`` vorher berechnet wurde und den Cache gefüllt hat.

Habe einfach aus Neugier getestet wie lange sehr große Zahlen brauchen berechnet zu werden und da ist es mir aufgefallen.
Habe zuerst mit der Funktion getestet und dann auf die Klasse gewechselt und wollte gucken, ob die Klasse langsamer ist als die Funktion.
Und da ich dann die Gleiche Zahl eingegeben hatte , was 400 war, habe ich gesehen, dass die Klasse weniger Rekursionstiefe "schafft".
Habe dann auch mal das Rekursionstiefenlimit erhöht und im Verhältnis von beiden das Gleiche Ergebnis gesehen.
Also bei Rekursionslimit 10000 war dann bei 5000 und 3333 Schluss.

Wie meinst Du das, dass es auch von der Historie abhängt.
Habe das Skript von der Konsole aus gestartet, da ist doch der Cache für die Berechnung beim Start immer leer.
An sich sollte sich memo doch von der kleinsten Zahl an anfangen zu füllen, da fib sich ja vorher immer selber aufruft, bis der Basisfall erreicht ist?
Daher ist doch 100 immer vor 200 im Cache, bzw. in memo?

@_Mala_Fide_: Was mit Historie gemeint ist habe ich doch mit einem Beispiel beschrieben. ``fib(200)`` hat zu einer Ausnahme geführt. ``fib(100)`` nicht. *Danach* ging dann auch ``fib(200)`` ohne eine Ausnahme auszulösen. Weil durch das ``fib(100)`` dann schon genug Zwischenergebnisse im Cache waren.

Also hast du im Prinzip fib wie folgt aufgerufen?

Code: Alles auswählen

print(fib(100))
print(fib(200))

Edit:
Ok, habe es gerade selbst getestet und es hat bis zu noch größeren Zahlen funktioniert.

Code: Alles auswählen

print(fib(332))
print(fib(664))
print(fib(996))

Kannst Du mir vielleicht noch etwas genauer erklären, warum die Klasse jetzt weniger Rekursionstiefe schafft, als die Funktion?
Du hattest zwar geschrieben, dass das Attributabrufen einen Schritt kostet, aber warum verbraucht das Abrufen Schritte?
Oder meinst Du damit, dass für die 1000 Schritte eine bestimmte Menge an Speicher reserviert ist, die Attributabfragen davon Speicher belegen und deswegen die maximale Anzahl an Schritten reduziert wird?

Das deutsche Python-Forum

Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren

Re: Uhnterschiedliche Rekusionstiefe Funktions- und Klassen-Memoization-Dekoratoren