Memoization

Kurz: Memoization speichert die Ergebnisse teurer Funktionsaufrufe zwischen: Wird die Funktion mit denselben Argumenten erneut aufgerufen, liefert sie das gespeicherte Ergebnis, statt neu zu rechnen.

Genauer: Das Verfahren funktioniert nur bei reinen Funktionen (Pure Functions), die bei gleicher Eingabe immer dasselbe zurückgeben. Den Speicher bildet meist eine Hashmap. Memoization macht die rekursive Fibonacci-Berechnung von exponentieller auf lineare Laufzeit schneller.

Im Detail

from functools import lru_cache
 
def fib_langsam(n):               # O(2^n): berechnet dieselben Werte immer wieder
    return n if n < 2 else fib_langsam(n - 1) + fib_langsam(n - 2)
 
@lru_cache(maxsize=None)
def fib(n):                       # O(n): jeder Wert wird nur einmal berechnet
    return n if n < 2 else fib(n - 1) + fib(n - 2)
 
print(fib(80))                    # 23416728348467685

Selbst gebaut (JavaScript)

function merke(f) {
  const cache = new Map();
  return (n) => {
    if (!cache.has(n)) cache.set(n, f(n));
    return cache.get(n);
  };
}
const quadrat = merke((n) => { console.log("rechne", n); return n * n; });
quadrat(4); // rechne 4
quadrat(4); // aus dem Cache, keine Ausgabe

Wann lohnt es sich?

• Gleiche Teilprobleme treten oft auf (dynamische Programmierung).
• Das Ergebnis hängt nur von den Argumenten ab.
• Der Speicher für den Cache ist vertretbar; manchmal begrenzt man ihn (LRU-Cache: die am längsten unbenutzten Einträge fliegen zuerst raus).

Siehe auch: Dynamische Programmierung, Rekursion, Hashmap, Pure Function