Memoisation: memorizzare nella cache i risultati ricorsivi

La versione ricorsiva ingenua di Fibonacci calcola più volte gli stessi valori. fib(5) chiama fib(4) e fib(3); fib(4) chiama fib(3) e fib(2) — quindi fib(3) viene calcolata due volte. Questa ridondanza cresce esponenzialmente: fib(40) esegue più di un miliardo di chiamate di funzione. La memoizzazione risolve il problema memorizzando ogni risultato la prima volta che viene calcolato, così le chiamate successive lo recuperano in O(1) invece di ricalcolarlo.

Aggiunga un dizionario memo come parametro (o utilizzi una closure). Prima del calcolo, verifichi se la risposta è già presente in memo. In caso affermativo, la restituisca immediatamente. In caso contrario, la calcoli, la memorizzi in memo e la restituisca. Ora ogni sottoproblema distinto viene calcolato esattamente una volta, trasformando O(2^n) in O(n) in termini di tempo e O(n) in termini di spazio per il dizionario memo, oltre a O(n) di spazio nello stack.

Python fornisce @functools.lru_cache(maxsize=None) (disponibile anche come @functools.cache in Python 3.9+) per automatizzare la memoizzazione. Aggiungendo questo decoratore sopra una funzione, tutte le chiamate vengono memorizzate in cache in base ai relativi argomenti. maxsize=None indica una dimensione illimitata della cache: ogni combinazione univoca di argomenti viene memorizzata. In questo modo qualsiasi funzione ricorsiva diventa una versione con memoizzazione con una sola riga di codice.

LeetCode 70 «Climbing Stairs»: è possibile salire 1 o 2 gradini alla volta. In quanti modi si può raggiungere il gradino n? In realtà, questo è un problema di Fibonacci: ways(n) = ways(n-1) + ways(n-2). Casi base: ways(0) = 1 (un modo per rimanere al piano terra), ways(1) = 1. Con la memoizzazione, la complessità è O(n) in termini di tempo e O(n) in termini di spazio.

LeetCode 322 «Coin Change»: date le denominazioni e un importo obiettivo, trovi il numero minimo di monete. Ricorsione memoizzata top-down: dp(amount) = 1 + min(dp(amount - coin)) per ogni moneta valida. Il caso base è dp(0) = 0. Memorizzi nella cache ogni sottoimporto. Se un sottoimporto è impossibile, restituisca infinito. La memoizzazione trasforma la forza bruta esponenziale in una complessità temporale pari a O(amount × len(coins)).

LeetCode 139 «Word Break»: determini se una stringa può essere segmentata in parole del dizionario. Ricorsione top-down: can_break(s, start) prova ogni prefisso s[start:end]; se il prefisso è nel dizionario e can_break(s, end) restituisce true, restituisca true. Senza memoizzazione la complessità è O(2^n); con la memoizzazione (memorizzando nella cache ogni indice di inizio) diventa O(n² × L), dove L è la lunghezza massima di una parola.

La memoizzazione (top-down) parte dal problema originale e memorizza nella cache le risposte man mano che vengono scoperte ricorsivamente. Risolve solo i sottoproblemi effettivamente necessari. La tabulazione (bottom-up) riempie in anticipo una tabella, dai sottoproblemi più piccoli a quelli più grandi, risolvendo tutti i sottoproblemi indistintamente. La memoizzazione è più facile da ricavare da una soluzione ricorsiva; la tabulazione evita i limiti della profondità della ricorsione e l'overhead delle chiamate di funzione.

Molti problemi di DP che la ricorsione con memoizzazione risolve usando O(n) di spazio possono essere ulteriormente ottimizzati fino a O(1) di spazio quando servono solo un numero fisso di risposte dei sottoproblemi precedenti. Per Fibonacci, contano solo gli ultimi due valori. Lo stesso vale per Climbing Stairs. Due variabili a scorrimento sostituiscono l'intero dizionario memo o la tabella.

Esistono tre modi per implementare manualmente la memoizzazione. Un dizionario globale è semplice, ma inquina l'ambito del modulo. Una closure incapsula la cache all'interno della funzione, impedendone la dispersione, ma richiede un wrapper. @lru_cache è la soluzione più pulita: un solo decoratore sostituisce tutto il codice ripetitivo. In un colloquio, inizi con @lru_cache, a meno che l'intervistatore non chieda esplicitamente un'implementazione manuale.

La memoizzazione accelera solo i problemi con sottoproblemi sovrapposti, cioè i casi in cui lo stesso sottoproblema viene calcolato più volte. Se ogni sottoproblema è univoco (come nel semplice attraversamento di un albero, in cui ogni nodo viene visitato esattamente una volta), la memoizzazione aggiunge overhead senza offrire vantaggi. Inoltre, la memoizzazione non può risolvere i problemi in cui l'albero ricorsivo è esponenziale nel numero di sottoproblemi distinti anziché nel riutilizzo: per questi problemi serve un algoritmo completamente diverso.

Applichi la memoizzazione quando: dispone di una soluzione ricorsiva corretta ma lenta a causa dei ricalcoli ridondanti, la funzione ha un numero ridotto di combinazioni distinte di argomenti e il valore restituito dipende solo dagli argomenti (funzione pura, senza effetti collaterali né stato globale). Verifichi lo spazio degli stati dei sottoproblemi: se esistono al massimo O(n) o O(n²) stati distinti, la memoizzazione converte il tempo esponenziale in tempo polinomiale.

Metta alla prova la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato che: la memoizzazione memorizza i risultati dei sottoproblemi per evitare i ricalcoli, convertendo la ricorsione esponenziale in tempo polinomiale, @functools.lru_cache è lo strumento idiomatico di Python e richiede una sola riga e la memoizzazione (top-down) e la tabulazione (bottom-up) sono i due stili della DP: la memoizzazione è più facile da ricavare, mentre la tabulazione evita i problemi legati alla profondità dello stack. Congratulazioni: ha completato i moduli sulla ricorsione e sulle hash map!