Die rekursive Definition der Fibonacci-Folge:
def fib(n):
return 1 if n < 3 else fib(n - 1) + fib(n - 2)
Lässt man die Werte nun per
for n in range(1, 100):
print("{} | {}".format(n, fib(n)))
ausgeben, stellt man fest, dass der Zeitbedarf der Berechnung ab etwa n = 30 in die Größenordnung von Sekunden ansteigt und ab etwa n = 40 Minuten beträgt. Die genauen Werte sind natürlich davon abhängig, wie schnell der Computer rechnen kann und wie der Interpreter implementiert ist.
Man kann zeigen, dass der Berechnungsaufwand exponentiell steigt. Trägt man also die logarithmierte Zeitdauer in Abhängigkeit von n auf, müsste sich eine Gerade ergeben. Bei der Messung sollte man die Zeitdauer über möglichst viele Berechnungen mitteln, um solche statistischen Effekte herauszurechnen, die durch das Betriebssystem und Vorgänge im Prozessor entstehen. Außerdem sollte man dafür sorgen, dass die Startzeit des Interpreters bzw. die Ladezeit des Programms nicht mit in die Messung eingeht.
Zur Reduktion des Berechnungsaufwands kommt nun Memoisierung zur Anwendung. Hierbei werden bereits berechnete Werte in einem Memo oder Cache gespeichert, um sie nicht ständig erneut ermitteln zu müssen. Als Speicher diene zunächst ein Array.
fib_memo = 1000*[None]
def fib(n):
if n < 3:
return 1
else:
if fib_memo[n] is None:
fib_memo[n] = fib(n - 1) + fib(n - 2)
return fib_memo[n]
Eleganter als die Festsetzung einer festen Arraygröße ist jedoch die Nutzung eines dynamischen Arrays oder eines Wörterbuchs. Ersetzt man das Array durch ein Wörterbuch, nimmt das Programm die folgende Gestalt an:
fib_memo = {}
def fib(n):
if n < 3:
return 1
else:
if not n in fib_memo:
fib_memo[n] = fib(n - 1) + fib(n - 2)
return fib_memo[n]
Bei der bisher beschriebenen Vorgehensweise verbleibt noch das Manko, dass die Memoisierung umständlich in jeden neuen Algorithmus eingefügt werden muss. Für den Leser wird der eigentliche Algorithmus dabei quasi mit technischem Balast verschleiert.
Wir beseitigen dieses Manko nun durch Abtrennung der Memoisierung
vom Algorithmus. Eine Funktion memoize erzeugt hierbei
eine neue Funktion, die die urspüngliche in eine Memoisierung
einhüllt. Dies gelingt folgendermaßen:
def memoize(f):
memo = {}
def f_memo(n):
if not n in memo: memo[n] = f(n)
return memo[n]
return f_memo
def fib(n):
return 1 if n < 3 else fib(n - 1) + fib(n - 2)
fib = memoize(fib)
Bequemerweise bietet die Sprache Python mit ihrer Dekorateur-Syntax abschließend noch einen syntaktischen Zucker, mit dem sich die Memoisierung ideal notieren lässt:
@memoize
def fib(n):
return 1 if n < 3 else fib(n - 1) + fib(n - 2)
Es sei erwähnt, dass die Formulierung von memoize
mehrstellige Funktionen einbezieht, wenn man die Argumente der
jeweiligen Funktion zu einem Tupel zusammenfasst. Man betrachte zur
Demonstration die rekursive Berechnung der Binomialkoeffizienten:
@memoize
def bc(t):
(n, k) = t
if k == 0 or k == n:
return 1
else:
return bc((n - 1, k - 1)) + bc((n - 1, k))
# Pascalsches Dreieck
for n in range(0, 10):
print([bc((n, k)) for k in range(0, n + 1)])
Mithilfe von Pythons Asterisk-Operator lässt sich
memoize überdies so verallgemeinern, dass mehrstellige
Funktion explizit einbezogen sind.
def memoize(f):
memo = {}
def f_memo(*t):
if not t in memo: memo[t] = f(*t)
return memo[t]
return f_memo
@memoize
def bc(n, k):
return 1 if k == 0 or k == n else bc(n - 1, k - 1) + bc(n - 1, k)
# Pascalsches Dreieck
for n in range(0, 10):
print([bc(n, k) for k in range(0, n + 1)])
Die Berücksichtigung benannter Argumente ist ebenfalls technisch machbar, gleichwohl der Mechanismus dadurch abermals ineffizienter wird. Da Wörterbücher in Python als veränderliche Objekte nicht als Schlüssel oder Bestandteil der Schlüssel von Wörterbüchern auftreten dürfen, muss das Wörterbuch der benannten Argumente zuvor in ein sortiertes Tupel umgewandelt werden.
def memoize(f):
memo = {}
def f_memo(*t, **d):
td = tuple(sorted(d.items()))
key = (t, td)
if not key in memo: memo[key] = f(*t, **d)
return memo[key]
return f_memo
In Pythons Standardbibliothek ist Memoisierung unter der
Bezeichnung cache im Modul functools
zu finden.
Besonders elgant wird die Formulierung, wenn die Anfangswerte
an memoize übergeben werden, womit die Fallunterscheidung
im jeweiligen Algorithmus entfallen darf. Das geht so:
def memoize(memo):
def cb(f):
def f_memo(n):
if not n in memo: memo[n] = f(n)
return memo[n]
return f_memo
return cb
@memoize({1: 1, 2: 1})
def fib(n):
return fib(n - 1) + fib(n - 2)
Zu erwähnen ist, dass auch der Aufruf der eigenen Funktion innerhalb der Rekursion gegen die memoisierte Variante ersetzt werden muss. Das war möglich, weil die Funktion auch innerhalb der Rekursion über eine globale Variable angesprochen wird. Ist dies nicht gegeben, kann man die Memoisierung alternativ in den Fixpunkt-Kombinator einbauen.
Zunächst der reine Fixpunkt-Kombinator:
def fix(cb):
def rec(n): return cb(rec, n)
return rec
@fix
def fib(rec, n):
return 1 if n < 3 else rec(n - 1) + rec(n - 2)
Nun bringen wir die Memoisierung ein und berücksichtigen mehrstellige Funktionen wieder mit der Asterisk-Syntax:
def fix(cb):
memo = {}
def rec(*t):
if not t in memo: memo[t] = cb(rec, *t)
return memo[t]
return rec
@fix
def fib(rec, n):
return 1 if n < 3 else rec(n - 1) + rec(n - 2)
Zur Konstruktion wechselseitiger Rekursion ist ein spezieller Fixpunkt-Kombinator zweckdienlich. Die Funktionen sind hierfür zu einer Struktur zusammenzufassen, die wir durch ein Wörterbuch darstellen.
def fix(cb):
rec = {}
rec.update(cb(rec))
return rec
s = fix(lambda rec: {
"even": lambda n: True if n == 0 else rec["odd"](n - 1),
"odd": lambda n: False if n == 0 else rec["even"](n - 1)
})
even = s["even"]
odd = s["odd"]
Die Memoisierung verläuft nun folgendermaßen:
def memo_fn(f):
memo = {}
def mf(*t):
if not t in memo: memo[t] = f(*t)
return memo[t]
return mf
def fix(cb):
rec = {}
for key, value in cb(rec).items():
rec[key] = memo_fn(value)
return rec
s = fix(lambda rec: {
"even": lambda n: True if n == 0 else rec["odd"](n - 1),
"odd": lambda n: False if n == 0 else rec["even"](n - 1)
})
even = s["even"]
odd = s["odd"]