Memoisation und Dekorateure


Definition der Memoisation

Brain Der Ausdruck "Memoisation" (englisch memoization) wurde im Jahre 1968 von Donald Michie geprägt. Der Ausdruck basiert auf dem lateinischen Wort "memorandum", was "das zu Errinnernde" bedeutet. Memoisation bezeichnet in der Informatik eine Technik, die in der Programmierung benutzt wird, um den Programmablauf zu beschleunigen. Dies wird erreicht, indem Berechnungsergebnisse gespeichert werden, wie zum Beispiel die Ergebnisse von Funktionsaufrufen. Wird eine Funktion mit den gleichen Parametern aufgerufen, wie bei einem vorigen Aufruf, wird auf die gespeicherten Ergebnisse zugegriffen statt die Werte neu zu berechnen. In vielen Fällen wird ein einfaches Array für die Ergebnisspeicherung benutzt, aber es sind auch kompliziertere Strukturen möglich. So können beispielsweise assoziative Arrays verwendet werden, die in Perl Hashes und in Python Dictionaries genannt werden.

Die Memoization kann explizit vom Programmierer programmiert werden, aber einige Programmiersprachen, wie auch Python, stellen Mechanismen zur Verfügung, die die Implementierung der Memoisation erleichtern.

Memoisation mit Dekorateur-Funktionen

In unserem vorigen Kapitel über rekursive Funktionen hatten wir eine iterative und eine rekursive Funktionsversion zur Berechnung der Fibonacci-Zahlen programmiert. Wir hatten gezeigt, dass die direkte Umsetzung der mathematischen Definition der Fibonacci Zahlen ein exponentielles Laufzeitverhalten aufzeigt, also eine Funktion wie die folgende:
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

In unserem Kapitel über Rekursion hatten wir auch einen Weg dargestellt, wie man das Laufzeitverhalten der rekursiven Version verbessern kann. Wir hatten ein Dictionary dazu verwendet, um bereits durch die Funktion berechnete Werte für spätere Aufrufe zu speichern. Dadurch wird eine Neuberechnung verhindert. Dabei handelte es sich bereits, ohne dass wir es so genannt hatten, um ein Beispiel, wie man explizit die Technik der Memoization nutzen kann. Die Methode hatte jedoch einen entscheidenden Nachteil: Die Klarheit und die Schönheit der ursprünglichen rekursiven Methode geht dabei verloren.

Das "Problem" besteht darin, dass wir den Code der rekursiven fib-Funktion ändern bzw. erweitern mussten. Im folgenden Code präsentieren wir eine Lösung, die ohne Änderungen der fib-Funktion auskommt. Dadurch wird ihre Klarheit, Schönheit und Lesbarkeit nicht tangiert. Zu diesem Zweck definieren wir eine Funktion, die wir memoize nennen. memoize() benötigt zwei Argumente. Auch die Funktion memoize benutzt ein Dictionary, um die Funktionswerte zu speichern. Obwohl sowohl die Variable "memo", - unser Dictionary zum Speichern der Werte, - als auch die Funktion "f" lokal innerhalb der Funktion memoize sind, werden ihre Werte durch die helper-Funktion bewahrt. Im Englischen benutzt man statt "bewahrt" das Wort "captured", was im Deutschen "eingefangen" oder "gefangen genommen" bedeutet. Diese Technik, d.h. das Bewahren von ,,lokalen'' Werten oder Funktionen über ihren lokalen Geltungsbereich hinaus wird auch als Closure oder Funktionsabschluss bezeichnet. memoize() liefert als Funktionswert eine Referenz auf die helper-Funktion zurück. Ein Aufruf der Funktion memoize(fib) liefert eine Funktion zurück, die im Ein- und Ausgabeverhalten identisch mit fib() ist, d.h. sie tut, was fib() tut. Zusätzlich speichert sie jedoch die Ergebnisse im memo-Dictionary.



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))


Als nächstem Punkt kommen wir zu einem Konzept, was als "Dekorateur" (englisch decorator: Raumgestalter, Dekorateur) bezeichnet wird. Schauen wir uns die folgende Codezeile an:
fib = memoize(fib)
In diesem Fall spricht man davon, dass die fib-Funktion durch die memoize-Funktion dekoriert wird.
In den folgenden Diagrammen verdeutlichen wir, was bei der Dekoration passiert. Im ersten Diagramm zeigen wir den Zustand der Funktionen vor der Dekoration. Wir sehen die Namen der Funktionen mit Referenzen auf ihre Funktionsbodies:

Funktionsweise der Memoizsation

Nach dem Ausführen der Zeile fib = memoize(fib) zeigt fib auf den Body der Helper-Funktion, der nach dem Aufruf memoize(fib) zurückgeliefert wird. Wir können außerdem erkennen, dass der Code der ursprünglichen Fib-Funktion nur noch durch f in der Helper-Funktion aufgerufen wird bzw. aufgerufen werden kann. Es gibt sonst keine Referenz mehr auf die ursprüngliche fib-Funktion. Im return-Statement return fib(n-1) + fib(n-2) wird nun die neue, dekorierte Fibonacci-Funktion aufgerufen, d.h. die von memoize zurückgelieferte helper-Funktion:

Funktionsweise der Memoizsation, 2. Diagramm

Ein weiterer Punkt im Zusammenhang mit Dekorateuren verdient auch besondere Erwähnung. In der Regel schreiben wir einen Dekorator nicht für einen speziellen Anwendungsfall sondern verwenden den Dekorator für viele Funktionen. So könnten wir beispielsweise weitere Funktionen haben, die alle viel Zeit für die Berechnung konsumieren, sagen wir func1, func2, func3 und so weiter. Es bietet sich dann an, alle mit unserer Dekoratorfunktion "memoize" zu dekorieren:
fib = memoize(fib)
func1 = memoize(func1)
func2 = memoize(func2)
func3 = memoize(func3)
# und so weiter


Memoize in einer Klasse

Dieses Unterkapitel kann von denen problemlos übersprungen werden, die sich noch nicht mit der Objektorientierung in Python beschäftigt haben.

Wir können das Zwischenspeichern der Ergebnisse auch in einer Klasse statt einer Funktion einkapseln. Wir demonstrieren dies im folgenden kleinen Beispiel:
class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if args not in self.memo:
        	self.memo[args] = self.fn(*args)
        return self.memo[args]

Da wir ein Dictionary verwenden, können wir keine veränderlichen (mutable) Argumente verwenden. Anders ausgedrückt: Die Argumente dürfen nur unveränderlich (immutable), also z.B. Tupel, sein.

Übliche Syntax für Dekorateure

Zusammenfassend können wir nun sagen, dass ein Dekorateur in Python ein aufrufbares Python-Objekt ist, welches benutzt wird, um eine Funktion, eine Methode oder eine Klassendefinition zu modifizieren. Das ursprüngliche Objekt, also das zu modifizierende, wird dem Dekorateur als Argument zugeführt. Der Dekorateur liefert ein modifiziertes Objekt zurück, also beispielsweise eine modifizierte Funktion. Dieses modifizierte Objekt wird an den Namen gebunden, der modifiziert wird.

Anders als in unserem obigen Beispiel werden die Dekoratorfunktionen nicht direkt aufgerufen, wie wir es oben getan haben, also in unserem Beispiel mit fib = memoize(fib). Stattdessend stellt man vor den Funktionsheader der zu dekorierenden Funktion eine Zeile mit dem Dekoratornamen. Dem Dekoratornamen wird aber ein "@" vorangestellt. Diese Zeile muss unmittelbar vor der zu dekorierenden Funktion stehen.

Wir schreiben nun unser anfängliches Beispiel entsprechend um. Wir dekorieren unsere fib-Funktion mit @memoize. Damit sieht unser Fibonacci-Beispiel wie folgt aus:
def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(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)

print(fib(40))


Weitere Beispiele mit Dekorateuren

Überprüfung von Argumenten durch Dekorateure

In unserem Kapitel über rekursive Funktionen hatten wir die Fakultätsfunktion eingeführt. Dabei wollten wir die Funktion so einfach wie möglich halten. Hätten wir die Argumente der Fakultätsfunktion auf Plausibilität geprüft, hätten wir die zugrunde liegende Idee verschleiert und der Kern des Algorithmus wäre nicht mehr so erkenntlich gewesen. So darf die Funktion keinesfalls mit negativen Werten oder Fließkommazahlen, also float-Werten, aufgerufen werden. In beiden Fällen kommt es zu einer endlosen Rekursion, die allerdings glücklicherweise durch den endlichen Rekursionsstack von Python mit einem RuntimeError abgebrochen wird:
RuntimeError: maximum recursion depth exceeded in comparison


Das folgende Programm benutzt eine Dekorateur-Funktion um sicherzustellen, dass es sich bei dem verwendeten Argument, um eine positive ganze Zahl handelt:
def argument_test_natural_number(f):
    def helper(x):
        if type(x) == int and x > 0:
            return f(x)
        else:
            raise Exception("Argument is not an integer")
    return helper
    
@argument_test_natural_number
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

for i in range(1,10):
    print(i, factorial(i))

print(factorial(-1))


Funktionsaufrufe mit Dekorateuren zählen

Im folgenden Beispiel zeigen wir, wie wir unter Benutzung eines Dekorateures elegant die Aufrufe einer Funktion bzw. einer Methode zählen können.
def call_counter(func):
    def helper(*args, **kwargs):
        helper.calls += 1
        return func(*args, **kwargs)
    helper.calls = 0
    helper.__name__= func.__name__

    return helper

@call_counter
def succ(x):
    return x + 1

print(succ.calls)
for i in range(10):
    print(succ(i))
    
print(succ.calls)
Die Ausgabe sieht wie folgt aus:
0
10