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 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 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 diesem Kapitel hatten wir auch einen Weg dargestellt, wie man das Laufzeitverhalten der rekursiven Version verbessern kann, indem man ein Dictionary hinzufügt, um bereits durch die Funktion berechnete Werte für spätere Aufrufe zu speichern. Dabei handelte es sich um ein Beispiel, wie man explizit die Technik der Memoization nutzt, aber wir hatten es nicht so genannt. Der Nachteil dieser Methode besteht darin, dass die Klarheit und die Schönheit der ursprünglichen rekursiven Methode verloren geht.

Das "Problem" besteht darin, dass wir den Code der rekursiven fib-Funktion ändern mussten. Der folgende Code kommt ohne Änderungen der fib-Funktion aus, sodass ihre Klarheit und Lesbarkeit nicht tangiert wird. Zu diesem Zweck nutzen wir eine Funktion, die wir memoize nennen. memoize() benötigt zwei Argumente. Die Funktion memoize benutzt ein Dictionary "memo", um die Funktionswerte zu speichern. Obwohl sowohl die Variable "memo", 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. 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 Codzeile an: 
fib = memoize(fib)
Man sagt in diesem Fall, dass die fib-Funktion durch die memoize-Funktion dekoriert wird.

Memoize in einer Class

Wir können das Zwischenspeichern der Ergebnisse auch in einer Klasse einkapseln. Dies demonstrieren wir im folgenden 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 Dekorateur-Syntax von Python 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. Unser Beispiel der fib-Funktion sieht nun wie folgt im Ganzen 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. Wir wollten nicht die zugrunde liegende Idee verschleiern, indem wir die Argumente auf Plausibilität geprüft hätten. Die Funktion darf nicht mit negativen Werten oder mit float-Werten aufgerufen werden, da dann eine Endlosschleife ausgeführt würde.

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