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)

We also presented a way to improve the runtime behaviour of the recursive version by adding a dictionary to memorize previously calculated values of the function. this was an example of explicitly using memoization, but we didn't call it like this. The disadvantage of this method was, that the clarity and the beauty of the original recursive implementation was lost.

The "problem" is, that we changed the code of the recursive fib function. The following code doesn't change our fib function, so that its clarity and legibility isn't touched. We use instead a function which we call memoize. memoize() takes a function as an argument. The function memoize uses a dictionary "memo" to store the function results. Though the variable "memo" as well as the funtion "f" are local to memoize, they captured by a closure through the helper function which is returned as a reference by memoize(). So, the call memoize(fib) returns a reference to the helper() which is doing what fib() would have done plus a wrapper which is saving the results, which are still not stored, in the memo dictionary and is preventing recalculation of results, which are already in memo. 

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


Now we come to what's called the decorator. Let's look at the line in our code were we assign memoize to fib: 
fib = memoize(fib)
One says, that the fib function is decorated by the the memoize() function.

Memoize as a Class

We can encapsulate the caching of the results in a class as well, as you can see in the following example: 
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]

As we are using a dictionary, we can't use mutable arguments, i.e. the arguments have to be immutable.

Decorators in Python

A decorator in Python is a callable Python object that is used to modify a function, method or class definition. The original object, the one which is going to be modified, is passed to a decorator as an argument. The decorator returns a modified object, e.g. a modiefied function, which is bound to the name used in the definition. Python decorators have a similar syntax than Java annotations. The decorator syntax in Python can be seen as pure syntactic sugar, using @ as the keyword.

Example: Using a Decorator for Memoization

We already had used a decorator without saying so. The memoize function in the example at the beginning of this chapter is a decorator. We used it to memorize the results from the fib function.

What we hadn't used was the special decorator syntax of Python, i.e. the at character "@"
Instead of writing the statement 
fib = memoize(fib)
we can write 
@memoize
But this line has to be directly in front of the decorated function, in our example fib(): 
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))

Checking Arguments with a Decorator

In our chapter about recursive functions we introduced the faculty function. We wanted to keep the function as simple as possible and we didn't want to obscure the underlying idea, so we hadn't incorporated any argument checks. So, if somebody had called our function with a negative argument or with a float argument, our function would have got into an endless loop.

The following program uses a decorator function to ensure that the argument passed to the function faculty is a positive integer: 
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 faculty(n):
    if n == 1:
        return 1
    else:
        return n * faculty(n-1)

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

print(faculty(-1))