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 è

fib(n) {
   if n is 1 or 2, return 1;
   return fib(n-1) + fib(n-2);
}

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

alloca array per memo, settando tutti i valori a zero;
inizializza memo[1] e memo[2] a 1;

fib(n) {
   if memo[n] diverso da 0, return memo[n];
   memo[n] = fib(n-1) + fib(n-2);
   return memo[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.

memoize(f) {
  alloca array per memo, settando tutti i valori a indefinito;
  costruisci una nuova funzione chiamata "temp":
  temp(*args) {
    if args not in memo {
       memo[args] = f(*args)
    }
    return memo[args]
  }
  return temp
}

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":

memofib = memoize(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:

def memoize(f):
    cache = {}
    def g(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return g

def fib(n):
    if n in [0, 1]: return n
    return fib(n-1)+fib(n-2)

fib = memoize(fib)

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 [1] o pulendo la cache solo quando ritorna l'ultima chiamata a f[2].

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:

> square(4), square(7); # vengono inserite due voci nella tabella
                     16, 49

> op(4, eval(square));  # richiama la tabella di remember e il suo contenuto
            table([4 = 16, 7 = 49])

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

Voci correlate

• Trasparenza referenziale
• Calcolo approssimato
• Programmazione dinamica
• Task skipping
• Loop perforation

Collegamenti esterni

• Memoize.pm - Un modulo Perl che implementa le subroutine memoizzate.
• Java memoization - un esempio in Java che utilizza classi proxy dinamiche per creare un pattern di memoizzazione generica.

Nota: Questo articolo contiene materiale preso da una voce di pubblico dominio del NIST Dictionary of Algorithms and Data Structures a http://www.nist.gov/dads/HTML/memoize.html