Memoisation and 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 ist eine Technik, die in der Programmierung benutzt wird, um den Programmablauf zu beschleunigen. Dies wird erreicht, indem Berechnungsergebnis 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 sind.

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. Der 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 wir 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.

Memoize in einer Klasse

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.

Decorateure in Python

Ein Dekorateur in Python ist ein aufrufbares Python-Objekt, das 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. Python-Dekorateure haben eine ähnliche Syntax wie in Java. Die Syntax der Dekorateure in Python kann als syntaktischer Zucker angesehen werden, indem man @ als Keywort verwendet.

Beispiel: Dekorateur für die Memoization

Wir hatten bereits einen Dekorateur benutzt, ohne es so zu nennen. Bei der memoize-Funktion, im Beispiel am Anfang dieses Kapitels unseres Tutorials, handelt es sich um einen Dekorateur.

Allerdings hatten wir in diesem Beispiel nicht die spezielle Syntax von Dekorateuren benutzt, also das "@"-Zeichen.
Statt der Anweisung
fib = memoize(fib)
können wir vereinfachend folgende Anweisung benutzen:
@memoize
Allerdings muss diese Zeile unmittelbar vor der dekorierten Funktion stehen. Nun können wir unsere fib-Funktion dekorieren. Mit Dekorateur sieht unsere Fibonacci-Funktion 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)

#fib = memoize(fib)

print(fib(40))

Überprüfung von Argumenten durch Dekorateure

In unserem Kapitel über rekursive Funktionen hatten wir die Fakultätsfuntion 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 abgebrochen 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))