Ci sono diversi articoli eccellenti che parlano della tecnica di ottimizzazione chiamata memoization. Potete accedervi qui e qui. Quello che faremo è darvi una breve panoramica di cosa sia la memoizzazione. Andremo un po’ oltre eseguendo un’analisi passo dopo passo di ciò che il codice “memoization” sta effettivamente facendo, linea per linea. Alla fine dell’articolo, capirete appieno la memoizzazione.

La memoizzazione è la pratica programmatica di rendere le lunghe funzioni ricorsive/iterative molto più veloci.

Come, vi chiederete? Mettendo nella cache i valori che la funzione restituisce dopo la sua esecuzione iniziale.

Quando inseriamo lo stesso valore nella nostra funzione memorizzata, essa restituisce il valore memorizzato nella cache invece di eseguire nuovamente la funzione, aumentando così le prestazioni. Non è più necessario che il vostro programma ricalcoli ogni numero per ottenere un risultato.

Sembra fantastico, vero? Beh, quello che è ancora meglio è che non è difficile capire cosa fa una funzione memoize una volta che si scompone il codice.

Ecco un esempio di una funzione memo di base:

Partiamo dall’inizio…

Stiamo restituendo quella che si chiama una chiusura anonima. La nostra chiusura anonima è in grado di ereditare qualsiasi variabile o, in questo caso, funzione passata in memo. Possiamo quindi giocare con l’oggetto argomenti che la nostra funzione passata fornisce.

Nota a margine: Quindi, se ogni funzione ha un oggetto argomenti, perché non stiamo ereditando l’oggetto argomenti di memo? Questo perché, come regola, le chiusure non ereditano l’oggetto argomenti di una funzione esterna. Usiamo questa regola a nostro vantaggio per giocare con la funzione che vogliamo memorizzare.

Sottolineiamo esattamente cosa fa la memorizzazione guardando un esempio molto semplice e poco pratico. A proposito, dovreste copiare/incollare questo codice, o qualsiasi codice, per avere un’idea di come funziona.

Credo che abbiamo capito il succo di questo esempio di codice. Praticamente parla da solo. Vediamo un po’ di più guardando un’istantanea di una vera funzione memo:

Ora che abbiamo capito cosa fa una funzione memo, creiamo un’espressione di funzione e passiamo una funzione Fibonacci ricorsiva in memo e vediamo cosa succede.

//Now we'll test our code!
// =======TEST=======
fib(10)//On the first try we need to load//=> loading…//=> loading…//=> loading…//=> loading…//=> loading…//=> 4 loadings later we get...//=> 89// And on the second try…fib(10)//=> 89//No loading! Yaay!//The cool thing about memoizing the recursive Fibonacci algorithm is that once we make a call for the value of the nth number in the series, we are able to store all the previous numbers in the series.//So if we try...
fib(7) //=> 21
//We don't have to recalculate anything.//And if we want to try fib(11)...
fib(11)
//loading...
//=> 144
//Our memoized recursive function already cached fib(1-10),so all it needed to do was to calculate the cached values. // This is what the cache now looks like:
/*
{ '{"0":0}': 1,
'{"0":1}': 1,
'{"0":2}': 2,
'{"0":3}': 3,
'{"0":4}': 5,
'{"0":5}': 8,
'{"0":6}': 13,
'{"0":7}': 21,
'{"0":8}': 34,
'{"0":9}': 55,
'{"0":10}': 89,
'{"0":11}': 144}
*/

Conclusione

La memorizzazione diventa demistificata quando la si riduce a coppie chiave-valore. Tutto quello che stiamo facendo è creare un oggetto, controllare i valori esistenti che corrispondono all’input dell’utente, e memorizzare nuove coppie chiave-valore se non esistono nel nostro oggetto.

Ovviamente, memorizzare tutti questi dati significa che stiamo consumando memoria. È meglio implementare la memoizzazione su funzioni che sono pure e comportano calcoli pesanti e ripetitivi.

Bonus:

Per divertimento, ecco una versione funzionale del nostro memoizer: