La memoizzazione, per quanto il computer e forse anche l'accademia della crusca la segnino come una parola sbagliata, è in realtà una tecnica di programmazione che spesso può salvare la vita di un programma e risparmiare tanto lavoro inutile al processore (con conseguente risparmio di qualche milione di anni di tempo di calcolo).
Consideriamo l'algoritmo ricorsivo classico (qui riportato in C per semplicità (???)) per il calcolo dell'n-esimo numero di
Un algoritmo senz'altro molto elegante e compatto, ma che cela al suo interno un odiosissimo dettaglio: il numero di chiamate ricorsive effettuate da questa funzione cresce insieme al valore di n, risultando così (e tralasciando i dettagli da informatica teorica) in un algoritmo pienamente esponenziale, che richiede tempo
(per esempio la chiamata a fibonacci(1) viene fatta proprio
volte). Come ci possiamo salvare quindi da questa nefasta sciagura che si abbatte inesorabilmente su chiunque abbia mai provato almeno una volta ad implementare un algoritmo per il calcolo dei numeri di Fibonacci? Con la memoizzazione.
In pratica questa tecnica si basa su un'idea molto banale e cioè quella che se si è già calcolato un risultato, questo non deve essere più ricalcolato ma salvato. Ecco quindi che ci basta introdurre un array in cui salviamo i risultati via via che li calcoliamo per tornare di nuovo nel paradiso degli algoritmi polinomiali, con un tempo pari a
:
(L'array è globale ma si potrebbe anche dichiarare static all'interno della funzione)
Ed ecco qui la nostra funzione memoizzata e più veloce rispetto all'algoritmo precedente. L'obiezione adesso è che usiamo anche
spazio, e infatti nella versione definitiva uno potrebbe limitarsi a salvare in due variabili temporanee i valori di fibonacci(n-1) e fibonacci(n-2) per ottenere spazio costante, ma questo non ha a che vedere con la memoizzazione in sé, il cui effetto è principalmente sul tempo di esecuzione e in base a cui l'algoritmo appena visto è perfetto.
Concludo dicendo che nei linguaggi che trattano le funzioni come "cittadini di prima classe" o "di serie A" è possibile costruire meccanicamente funzioni memoizzate tramite una funzione memoize(f) che prende in input la funzione da memoizzare e resituisce una nuova funzione che funzionerà più o meno come quella per il calcolo del numero di Fibonacci (cioè calcola una sola volta i valori e quando essi siano già stati calcolati vengono subito restituiti). Uno pseudo-codice per la funzione memoize() si può trovare nella
Consideriamo l'algoritmo ricorsivo classico (qui riportato in C per semplicità (???)) per il calcolo dell'n-esimo numero di
Perfavore,
Entra
oppure
Registrati
per vedere i Link!
che discende direttamente dalla definizione della successione:
C:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
In pratica questa tecnica si basa su un'idea molto banale e cioè quella che se si è già calcolato un risultato, questo non deve essere più ricalcolato ma salvato. Ecco quindi che ci basta introdurre un array in cui salviamo i risultati via via che li calcoliamo per tornare di nuovo nel paradiso degli algoritmi polinomiali, con un tempo pari a
C:
Perfavore,
Entra
oppure
Registrati
per vedere i codici!
Ed ecco qui la nostra funzione memoizzata e più veloce rispetto all'algoritmo precedente. L'obiezione adesso è che usiamo anche
Concludo dicendo che nei linguaggi che trattano le funzioni come "cittadini di prima classe" o "di serie A" è possibile costruire meccanicamente funzioni memoizzate tramite una funzione memoize(f) che prende in input la funzione da memoizzare e resituisce una nuova funzione che funzionerà più o meno come quella per il calcolo del numero di Fibonacci (cioè calcola una sola volta i valori e quando essi siano già stati calcolati vengono subito restituiti). Uno pseudo-codice per la funzione memoize() si può trovare nella
Perfavore,
Entra
oppure
Registrati
per vedere i Link!
relativa alla memoizzazione.
