Memoisierung

Was ist Memoisierung?

Memoisierung ist eine Optimierungstechnik, bei der die Ergebnisse von (oft rechenintensiven) Funktionsaufrufen zwischengespeichert werden. Wenn die Funktion später erneut mit denselben Eingabeparametern aufgerufen wird, wird das gespeicherte Ergebnis zurückgegeben, anstatt die Berechnung erneut durchzuführen. Man "merkt" sich quasi die Ergebnisse – daher der Name (vom lateinischen "memorandum").

Fibonacci-Zahlen

Memoisierung ist besonders nützlich bei rekursiven Funktionen, bei denen dieselben Teilprobleme mehrfach gelöst werden müssen. Ein klassisches Beispiel ist die Berechnung der Fibonacci-Zahlen.

Naive rekursive Fibonacci-Berechnung:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Diese naive Implementierung hat keine gute Laufzeit, da z.B. bei der Berechnung von fibonacci(5) insgesamt zwei Mal fibonacci(3) aufgerufen wird. Einmal im zweiten rekursiven Aufruf und einmal als Teil von fibonacci(4).

Um die redundanten Berechnungen zu vermeiden, können wir ein Array, oder eine andere Datenstruktur wie eine Map oder ein Dictionary, verwenden, um die bereits berechneten Fibonacci-Zahlen zu speichern.

def fibonacci(n, memo):
    if n <= 1:
        return n

    # Prüfen, ob das Ergebnis bereits gespeichert ist
    if memo[n] != 0:
        return memo[n]

    # Neues Ergebnis speichern und zurückgeben
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

Durch die Memoisierung wird jede Fibonacci-Zahl $\leq n$ nur genau einmal berechnet. Dadurch reduziert sich die Laufzeit deutlich. Wir sagen, die Laufzeit ist linear, weil sie linear mit der Eingabegröße wächst. Dafür haben wir jetzt, im Vergleich zur naiven Implementierungen, einen (ebenfalls linearen) Speicherbedarf, den wir vorher nicht hatten. Tatsächlich ist es häufig so, dass wir mit Speicherplatz "dafür bezahlen", dass unsere Funktionen schneller berechnet werden können.

Collatz-Folge

Die Collatz-Folge, auch bekannt als das $(3n+1)$-Problem, ist eine Zahlenfolge, die für eine beliebige positive ganze Zahl $n$ wie folgt definiert ist:

• Wenn $n$ gerade ist, ist das nächste Glied der Folge $n/2$.
• Wenn $n$ ungerade ist, ist das nächste Glied der Folge $3n+1$.

Die Collatz-Vermutung besagt, dass diese Folge, egal mit welcher positiven ganzen Zahl man beginnt, schließlich immer die Zahl 1 erreicht.

Auch für das Collatz-Problem (oder die Collatz-Folge) ist Memoisierung sehr nützlich. Wenn wir die Länge der Folge bis zum Erreichen der 1 für verschiedene Startzahlen berechnen, können dieselben Zwischenzahlen in den Sequenzen verschiedener Startwerte auftauchen. Kennt man die Länge einer Collatz-Folge ab einer bestimmten Zahl bereits, kann dieser Wert direkt wiederverwendet werden.

Betrachten wir die Berechnung der Anzahl der Zahlen in der Folge (inklusive der 1):

• Folge für Startwert 6: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 (Länge: 9 Zahlen)
• Folge für Startwert 7: 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → ...
  Wenn wir bei der Berechnung für 7 die Zahl 10 erreichen, und die Länge der Folge ab 10 (also 10 → 5 → ... → 1) bereits bekannt ist, können wir diese nutzen.

Implementierung mit Memoisierung in Python:

# Ein Dictionary, um bereits berechnete Längen zu speichern
memo = {1: 1}  # Basisfall: Die Länge der Folge von 1 bis 1 ist 1

def collatz_steps(n):
    if n in memo:
        return memo[n]

    if n % 2 == 0:
        next_n = n // 2
    else:
        next_n = 3 * n + 1
    
    # Neues Ergebnis speichern und zurückgeben
    length = 1 + collatz_steps(next_n)
    memo_collatz[n] = length  
    return length

In diesem Beispiel wird ein Dictionary memo verwendet, um die Längen der bereits berechneten Collatz-Folgen zu speichern. Der Basisfall ist memo = {1: 1}, da die Folge für die Zahl 1 nur die 1 selbst enthält und somit die Länge 1 hat. Für jede neue Zahl n wird zuerst geprüft, ob ihre Folgelänge schon bekannt ist. Wenn nicht, wird die nächste Zahl in der Collatz-Folge berechnet und die Funktion rekursiv aufgerufen. Das Ergebnis (1 + Länge der Restfolge) wird dann für n im Dictionary gespeichert und zurückgegeben.

So wird, ähnlich wie bei den Fibonacci-Zahlen, jede Teillänge nur einmal berechnet, was die Effizienz bei der Berechnung für viele oder lange Folgen deutlich steigert. Wollen wir nicht die Länge zurückgeben, sondern die Sequenz an Zahlen, können wir einen komplett analogen Ansatz wählen.