Implementare la memoization in Python

La memoization è una tecnica di ottimizzazione che consiste nel memorizzare i risultati di funzioni costose (in termini di tempo di calcolo) e nel riutilizzarli quando la funzione viene richiamata con gli stessi argomenti. In Python è molto semplice da implementare e, se usata correttamente, può migliorare drasticamente le prestazioni di alcuni algoritmi, soprattutto quelli ricorsivi.

Quando ha senso usare la memoization

La memoization è particolarmente utile quando:

La funzione è pura: a parità di argomenti, restituisce sempre lo stesso risultato.
La funzione viene chiamata spesso con gli stessi argomenti.
Il costo di calcolo è elevato rispetto al costo di accesso alla cache.

Un esempio classico è il calcolo ricorsivo dei numeri di Fibonacci, dove molte chiamate ripetono gli stessi calcoli.

Prima di tutto: un esempio senza memoization

Consideriamo una semplice implementazione ricorsiva della funzione di Fibonacci:

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Questa implementazione è elegante ma estremamente inefficiente per valori di n moderatamente grandi (ad esempio 35 o 40), perché ricalcola più volte gli stessi risultati.

Memoization manuale con un dizionario

Il modo più diretto per fare memoization è usare un dict come cache. L idea è semplice:

Prima di calcolare il risultato, controlliamo se è già presente in cache.
Se è presente, lo restituiamo subito.
Se non è presente, lo calcoliamo, lo salviamo in cache, poi lo restituiamo.

from typing import Dict

_cache: Dict[int, int] = {}

def fib_memo(n: int) -> int:
    if n in _cache:
        return _cache[n]

    if n <= 1:
        result = n
    else:
        result = fib_memo(n - 1) + fib_memo(n - 2)

    _cache[n] = result
    return result

Con questa semplice modifica passiamo da una complessità esponenziale a una complessità lineare in n, perché ogni valore viene calcolato una sola volta.

Generalizzare la memoization con un decorator

Scrivere manualmente la cache per ogni funzione può essere noioso. In Python possiamo sfruttare i decorator per incapsulare la logica di memoization e riutilizzarla ovunque.

Un semplice decorator di memoization

from typing import Callable, Dict, Tuple, Any

def memoize(func: Callable) -> Callable:
    cache: Dict[Tuple[Any, ...], Any] = {}

    def wrapper(*args: Any) -> Any:
        if args in cache:
            return cache[args]

        result = func(*args)
        cache[args] = result
        return result

    return wrapper

Cosa succede qui:

cache è un dizionario che usa come chiave la tupla degli argomenti args.
Se la tupla è già presente in cache, restituiamo il valore salvato.
Altrimenti calcoliamo il risultato, lo salviamo e lo restituiamo.

Ora possiamo usare il decorator su qualunque funzione adatta alla memoization:

@memoize
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Da questo momento in poi, ogni chiamata a fib con un certo valore di n verrà calcolata al massimo una volta.

Aggiungere type hints e conservare i metadati della funzione

La versione precedente del decorator funziona, ma non conserva il nome e la docstring della funzione originale. Per farlo in modo pulito possiamo usare functools.wraps:

from functools import wraps
from typing import TypeVar, Callable, Dict, Tuple, Any

F = TypeVar("F", bound=Callable[..., Any])

def memoize(func: F) -> F:
    cache: Dict[Tuple[Any, ...], Any] = {}

    @wraps(func)
    def wrapper(*args: Any, **kwargs: Any) -> Any:
        key = (args, tuple(sorted(kwargs.items())))
        if key in cache:
            return cache[key]

        result = func(*args, **kwargs)
        cache[key] = result
        return result

    return wrapper  # type: ignore[return-value]

Note importanti:

Ora consideriamo anche i keyword argument (kwargs).
Costruiamo una chiave hashable usando una tupla con argomenti posizionali e una tupla ordinata di coppie chiave-valore per i keyword.
Usiamo @wraps(func) per conservare nome, docstring e altri attributi.

Usare functools.lru_cache

Python fornisce già un decorator di memoization molto potente: functools.lru_cache. Oltre a memorizzare i risultati, gestisce automaticamente la dimensione massima della cache con una politica di tipo Least Recently Used (LRU).

from functools import lru_cache

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

Alcuni dettagli utili:

maxsize=None significa che la cache può crescere senza limiti.
Possiamo scegliere una dimensione finita, ad esempio maxsize=128, per evitare un uso eccessivo di memoria.
La funzione decorata espone metodi come cache_info() e cache_clear().

Esempio di utilizzo di questi metodi:

from functools import lru_cache

@lru_cache(maxsize=128)
def expensive_operation(x: int) -> int:
    print("Calcolo...")
    return x * x

expensive_operation(10)  # Stampa "Calcolo..."
expensive_operation(10)  # Usa la cache, non ristampa

info = expensive_operation.cache_info()
print(info)  # Mostra statistiche sulla cache

Memoization con metodi di classe e di istanza

La memoization funziona bene anche con i metodi, ma bisogna ricordare che il primo argomento è self (per i metodi di istanza) o cls (per i metodi di classe). Se usiamo un decorator che include tutti gli argomenti nella chiave della cache, oggetti diversi avranno cache separate:

from functools import lru_cache

class PathCounter:
    def __init__(self, grid_size: int) -> None:
        self.grid_size = grid_size

    @lru_cache(maxsize=None)
    def count_paths(self, x: int, y: int) -> int:
        if x == self.grid_size or y == self.grid_size:
            return 1
        return self.count_paths(x + 1, y) + self.count_paths(x, y + 1)

Qui self fa parte della chiave della cache, quindi ogni istanza avrà una cache logica distinta, gestita automaticamente da lru_cache.

Attenzione agli argomenti non hashable

Per usare una struttura come il dict (e quindi anche lru_cache), le chiavi devono essere hashable. Ciò significa che non possiamo usare direttamente liste o dizionari come parte della chiave.

Ad esempio, questo codice solleverebbe un errore:

@memoize
def sum_list(values: list[int]) -> int:
    return sum(values)

Per aggirare il problema possiamo convertire gli argomenti non hashable in forme hashable, ad esempio trasformando le liste in tuple:

from functools import lru_cache
from typing import Tuple

@lru_cache(maxsize=None)
def sum_tuple(values: Tuple[int, ...]) -> int:
    return sum(values)

result = sum_tuple(tuple([1, 2, 3]))

Costi, benefici e limiti della memoization

La memoization non è una bacchetta magica: va usata quando il guadagno in tempo giustifica il costo in memoria. Alcuni aspetti da considerare:

Uso di memoria: la cache cresce con il numero di combinazioni di argomenti diversi. Con lru_cache possiamo limitarne la dimensione.
Funzioni non pure: se una funzione ha effetti collaterali o dipende dallo stato esterno (file, rete, tempo, variabili globali), la memoization può restituire risultati non aggiornati.
Overhead: per funzioni molto semplici e poco costose, la gestione della cache può essere più costosa del calcolo stesso.

Strategia pratica per introdurre la memoization

Identificare le funzioni lente tramite misurazioni (profiling, timing).
Verificare che siano funzioni abbastanza pure o comunque con output stabile.
Applicare inizialmente functools.lru_cache, semplice e ben testato.
Controllare gli effetti su prestazioni e memoria.
Se servono logiche particolari (invalidazione custom, cache per utente, ecc.), valutare un decorator personalizzato.

Conclusione

Implementare la memoization in Python è relativamente semplice, sia in modo manuale con un dizionario, sia tramite decorator personalizzati, sia sfruttando strumenti pronti come functools.lru_cache. Usata con criterio, la memoization permette di trasformare algoritmi potenzialmente troppo lenti in soluzioni efficienti e praticabili, con pochissime modifiche al codice esistente.