memosiation

[_Mala_Fide_]

Hallo,

bin gerade bei dem Python 2 Kurs der Seite http://www.python-kurs.eu beim Kapitel "Memoisation und Python-Dekorateure".
Memoziation an sich verstehe ich, ich verstehe nur den Aufruf der Funktion nicht.

Code: Alles auswählen

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

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

fib = memoize(fib)

print(fib(40))

Der memoize-Funktion wird ein Parameter übergeben und der helper-Funktion auch.
Um herrauszufinden wie der Aufruf Funktioniert habe ich die Funktion ohne Dekorateur versucht aufzurufen.
Mit folgendem Code wird die gewollte Ausgabe erzeugt.

Code: Alles auswählen

print memoize(fib)(40)

So kenne ich den Aufruf einer Funktion nicht. Kann mir bitte einer erklären warum und wie das funktioniert.

Mfg

_Mala_Fide_

[Dav1d]

Man muss Funktionen nicht unbeding aufrufen, man kann Funktionen z.B. auch in Listen oder Dictionaries packen:

Code: Alles auswählen

def foo():
    print('I am foo')

x = [foo]
y = {'name': foo}

x[0]()
y['name']()

Sowas ähnliches passiert hier. Man kann Funktionen nämlich nicht nur in Listen etc. packen sondern auch von anderen Funktionen zurückgeben:

Code: Alles auswählen

def foo():
    print('I am foo')

def bar():
    print('In bar')
    return foo

some_func = bar()
some_func() # <- hier wird tatsächlich foo aufgerufen
bar()() # <- das Gleiche in kürzer

Und genau das macht memoize, es gibt eine Funktion zurück, nur dass die Funktion halt erst in memoize definiert wird. Das hat den Vorteil, dass die Funktion `helper` einzigartig wird (es wird immer eine andere Funktion von memoize zurückgegeben, z.B. versuch dir 2-mal das Ergebnis von `memoize(fib)` auszugeben).

Das ergebnis von `memoize(fib)` ist also wieder eine andere Funktion (die Funktion `handler`), diese Funktion ruft dann deine Funktion `fib` auf und merkt sich das Ergebnis für jedes Argument und gibt dises zurück falls das Ergebniss schon bekannt ist anstatt `fib` erneut aufzurufen.

[BlackJack]

Vielleicht noch als Stichwort nach dem man suchen kann: Closure.

[_Mala_Fide_]

Danke für die schnellen Antworten und die gute Erklärung.

Wenn ich das richtig verstehe, wird memoize mit fib aufgerufen. Der übergebene Wert 40 wird an helper übergeben. Wenn sich der fib Wert für 40 bereits in memo befindet wird er ausgegeben, ansonsten wird fib von helper ausgeführt und der neue Wert an das dictionary memo übergeben.

Dann sollte, wenn ich die Funktion erst mit 40 und dann mit 41 aufrufe, nur der 41_te Wert berechnet werden, da die anderen 40 bereits in memo gespeichert sind