Memoizzazione
# Memoizzazione

La memoizzazione è una tecnica di programmazione che consiste nel salvare in memoria i valori restituiti da una funzione in modo da averli a disposizione per un riutilizzo successivo senza doverli ricalcolare. Memoizzazione, che significa letteralmente "mettere in memoria" è una tecnica caratteristica della programmazione dinamica. Spesso questo termine viene confuso con "memorizzazione" che, sebbene descriva lo stesso procedimento, ha un significato più ampio.

Una funzione può essere "memoizzata" soltanto se soddisfa la trasparenza referenziale, cioè se non ha effetti collaterali e restituisce sempre lo stesso valore quando riceve in input gli stessi parametri. Le operazioni che non soddisfano questa condizione, ma i cui valori restituiti hanno una piccola probabilità di cambiare, possono ancora essere duplicate ("cached", dal francese caché) usando tecniche più complesse. In generale, i risultati memoizzati non perdono di validità nel tempo, mentre, al contrario, quelli duplicati la perdono.

Nei linguaggi di programmazione funzionale è possibile costruire una funzione di livello superiore memoize che, a sua volta, creerà automaticamente funzioni memoizzate per ogni funzione dotata di trasparenza referenziale. Al contrario, invece, nei linguaggi privi di funzioni di ordine superiore, la memoizzazione deve essere implementata separatamente per ciascuna funzione che ne deve beneficiare.

La tecnica è anche spesso utilizzata nell'approccio top-down in programmazione dinamica.

## Esempio

Un programma banale per calcolare i numeri di Fibonacci è

Poiché fib è più volte ricalcolato sullo stesso argomento, il tempo di esecuzione per questo programma è $Ω(1.6^n).$ Se, invece, memoizziamo (salviamo) il valore di fib(n) la prima volta che viene calcolato il tempo di esecuzione scende a Θ(n).

In un linguaggio dotato di chiusure e funzioni di ordine superiore, la memoizzazione di qualunque funzione può essere definita automaticamente. Questa "memoize" costruisce e ritorna un'altra funzione che effettua la memoizzazione dell'argomento f.

La notazione *args qui intende rappresentare un argomento resto come in Python o in Common Lisp. Questa soluzione si basa sulla restituzione di un closure sulla variabile memo che funge da cache per la funzione restituita.

Questa funzione "memoize" può essere utilizzata per costruire una versione memoizzata di "fib":

Il calcolo dei numeri di Fibonacci può essere comunque fatto in tempo logaritmico (vedere la successione di Fibonacci); questo esempio è solo allo scopo di illustrare il concetto di memoizzazione.

## Implementazioni d'esempio

### Python

Un banale esempio di memoizzazione in Python, utilizzando scope innestati:

Questo banale memoizzatore utilizza quantità sempre crescenti di memoria, poiché i vecchi elementi non sono mai rimossi dalla cache. L'utilizzo della memoria può essere migliorato utilizzando uno schema di sgombero della cache, mantenendo i risultati solo per un tempo prespecificato o pulendo la cache solo quando ritorna l'ultima chiamata a f.

### Maple

Il sistema algebrico per computer Maple ha un memoizzatore incorporato, attraverso l'uso delle cosiddette tabelle di remember. Per esempio, definiamo una procedura 'square' come segue:

square := proc(x) option remember; x^2; end proc:

Dopodiché ogni chiamata a 'square' causa l'inserimento nella tabella della funzione per un riutilizzo successivo. Questa tabella può anche essere estratta:

## Storia

Il termine "memoizzazione" (memoization) è stato coniato da Donald Michie nel suo articolo "Memo functions and machine learning" (1968) su Nature.

## Utilizzi

* Ricerca
* Generazione di codice sorgente, incluso HTML
* Computazioni ripetitive, come ad esempio conversione di immagini, crittografia e compressione dati.
* Riconoscimento di pattern come ad esempio nel riconoscimento vocale
* Valutazione degli alberi di gioco
