Antwort.

Historie der Frage:

Memoization ist eine Optimierungstechnik, die häufig in der funktionalen Programmierung, rekursiven Berechnungen und dynamischen Programmierung angewendet wird, wenn dieselben Funktionen wiederholt mit denselben Argumenten aufgerufen werden. In Python wurde sie mit dem Erscheinen des Decorators functools.lru_cache und Patterns zur Zwischenspeicherung von Berechnungsergebnissen populär.

Problem:

Ohne Caching arbeiten rekursive Funktionen wie die Berechnung von Fibonacci-Zahlen sehr langsam: Für jedes Berechnungsargument werden viele Berechnungen wiederholt, was zu einem exponentiellen Anstieg der Aufrufanzahl führt.

Lösung:

Memoization speichert bereits berechnete Werte (z.B. in einem Dictionary), um sie bei Bedarf wiederzuverwenden:

Beispiel einer manuellen Implementierung:

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib(n-1) + fib(n-2)
    memo[n] = result
    return result

Ab Python 3.2 kann man einfach den Decorator verwenden:

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Wichtige Eigenschaften:

Erlaubt es, rekursive oder rechenintensive Funktionen zu beschleunigen, ohne ihre Logik zu ändern
Die Implementierung kann manuell (mit einem Dictionary) oder automatisch (über lru_cache) sein
Man sollte vorsichtig mit veränderlichen Argumenten sein, da lru_cache nur mit hashierbaren (unveränderlichen) Argumenten funktioniert.

Trickfragen.

Kann man eine Funktion mit veränderlichen Argumenten (z.B. Listen) memoizieren?

Nein, lru_cache erfordert, dass alle Argumente hashierbar (unveränderlich) sind, andernfalls wird ein TypeError erzeugt.

from functools import lru_cache

@lru_cache
# def f(a): return a[0]  # TypeError: unhashable type: 'list'

Werden memoizierte Werte automatisch gelöscht?

Ja, wenn eine maxsize festgelegt ist – die Werte, die das Limit überschreiten, werden gelöscht (Least Recently Used). Ein unendlicher Cache (maxsize=None) kann zu einem Speicherüberlauf führen.

Was passiert, wenn die memoizierte Funktion sich selbst mit neuen Argumenten aufruft?

Memoization funktioniert immer noch – für jedes einzigartige Argumenten-Set wird das Ergebnis nur einmal berechnet und zwischengespeichert.

Typische Fehler und Anti-Patterns

Memoization ohne Cache-Limit verwenden und den Speicher überfüllen
Versuchen, Funktionen mit veränderlichen Argumenten zu memoizieren
Vergessen, den Cache zu bereinigen, wenn er nicht mehr benötigt wird.

Beispiel aus dem Leben

Negativer Fall

Eigenes Caching ohne Größenbegrenzung implementieren:

cache = {}
def foo(x):
    if x not in cache:
        cache[x] = long_heavy_computation(x)
    return cache[x]

Nach einiger Zeit verwendet das Programm Gigabytes an Speicher.

Vorteile:

Schnelle Ausführung bei wiederholten Aufrufen.

Nachteile:

Unbegrenztes Speichervolumen
Möglicher Out of Memory.

Positiver Fall

Verwendung von lru_cache mit maxsize:

from functools import lru_cache

@lru_cache(maxsize=1000)
def foo(x):
    return long_heavy_computation(x)