Antwoord.

Geschiedenis van de vraag:

Memoization is een optimalisatietechniek die veel wordt toegepast in functioneel programmeren, recursieve berekeningen en dynamisch programmeren, wanneer dezelfde functies herhaaldelijk met dezelfde argumenten worden aangeroepen. In Python werd dit gebruikelijk met de introductie van de decorateur functools.lru_cache en patronen voor het cachen van berekeningsresultaten.

Probleem:

Zonder caching werken recursieve functies zoals het berekenen van Fibonacci-getallen zeer langzaam: voor elke argument worden berekeningen meerdere keren herhaald, wat leidt tot een exponentiële groei van het aantal aanroepen.

Oplossing:

Memoization slaat al berekende waarden op (bijvoorbeeld in een woordenboek), zodat ze opnieuw kunnen worden gebruikt wanneer dat nodig is:

Voorbeeld van handmatige implementatie:

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

Met Python 3.2 kan je eenvoudig de decorateur gebruiken:

from functools import lru_cache

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

Belangrijkste kenmerken:

Maakt het mogelijk om recursieve of computationeel zware functies te versnellen zonder hun logica te veranderen
Implementatie kan handmatig (met een woordenboek) of automatisch (via lru_cache) zijn
Wees voorzichtig met mutabele argumenten, omdat lru_cache alleen werkt met hashbare (immutable) argumenten

Vragen met een haakje.

Kan je een functie met mutabele argumenten (bijvoorbeeld lijsten) memoizeren?

Nee, lru_cache vereist dat alle argumenten hashbaar (immutable) zijn, anders krijg je een TypeError.

from functools import lru_cache

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

Worden memoized waarden automatisch verwijderd?

Ja, als maxsize is ingesteld — waarden die buiten de limiet vallen worden verwijderd (Least Recently Used). Een oneindige cache (maxsize=None) kan leiden tot geheugenoverloop.

Wat gebeurt er als een memoized functie zichzelf aanroept met nieuwe argumenten?

Memoization werkt nog steeds — voor elke unieke set argumenten wordt het resultaat slechts één keer berekend en gecached.

Typische fouten en anti-patronen

Memoization gebruiken zonder cachelimiet en geheugen volstoppen
Proberen functies met mutabele argumenten te memoizeren
Vergeten om de cache op te schonen wanneer deze niet meer nodig is

Voorbeeld uit het leven

Negatieve case

Eigen cache schrijven zonder groottebeperkingen:

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

Na verloop van tijd gebruikt het programma gigabytes aan geheugen.

Voordelen:

Werkt snel voor herhaalde aanroepen

Nadelen:

Ongelimiteerde groei van geheugen
Kans op Out of Memory

Positieve case

Gebruik van lru_cache met maxsize:

from functools import lru_cache

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