Risposta.

Storia della domanda:

La memoizzazione è una tecnica di ottimizzazione ampiamente utilizzata nella programmazione funzionale, nei calcoli ricorsivi e nella programmazione dinamica, quando le stesse funzioni vengono chiamate ripetutamente con gli stessi argomenti. In Python è entrata in uso con l'arrivo del decoratore functools.lru_cache e dei modelli di memorizzazione dei risultati dei calcoli.

Problema:

Senza la memorizzazione, le funzioni ricorsive, come il calcolo dei numeri di Fibonacci, funzionano molto lentamente: per ogni argomento, i calcoli vengono ripetuti molte volte, portando a una crescita esponenziale nel numero di chiamate.

Soluzione:

La memoizzazione memorizza i valori già calcolati (ad esempio, in un dizionario) per riutilizzarli quando necessario:

Esempio di implementazione manuale:

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

Con Python 3.2 è possibile utilizzare semplicemente il decoratore:

from functools import lru_cache

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

Caratteristiche chiave:

Permette di accelerare le funzioni ricorsive o computazionalmente intensive senza modificare la loro logica
L'implementazione può essere manuale (con un dizionario) o automatica (tramite lru_cache)
È necessario prestare attenzione agli argomenti mutabili, poiché lru_cache funziona solo con argomenti hashabili (immutabili)

Domande trabocchetto.

È possibile memoizzare una funzione con argomenti mutabili (ad esempio, liste)?

No, lru_cache richiede che tutti gli argomenti siano hashabili (immutabili), altrimenti si ottiene TypeError.

from functools import lru_cache

@lru_cache
# def f(a): return a[0]  # TypeError: tipo non hashable: 'lista'

I valori memoizzati vengono rimossi automaticamente?

Sì, se viene impostato maxsize, i valori che superano il limite vengono rimossi (Least Recently Used). Una cache infinita (maxsize=None) può portare a un overflow di memoria.

Cosa succede se una funzione memoizzata si richiama da sola con nuovi argomenti?

La memoizzazione funzionerà comunque: per ogni insieme unico di argomenti, il risultato viene calcolato solo una volta e memorizzato.

Errori comuni e anti-pattern

Utilizzare la memoizzazione senza limitare la cache e riempire la memoria
Tentare di memoizzare funzioni con argomenti mutabili
Dimenticare di pulire la cache quando non è più necessaria

Esempio dalla vita reale

Caso negativo

Si scrive una propria cache senza limitare la dimensione:

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

dopo un po' il programma utilizza gigabyte di memoria.

Vantaggi:

Funziona rapidamente per chiamate ripetute

Svantaggi:

Crescita illimitata della memoria
Possibile Out of Memory

Caso positivo

Utilizzo di lru_cache con maxsize:

from functools import lru_cache

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