32
What is memoization? Under what circumstances can it be useful and how can it be used? (If possible, illustrate with a simple example)
32
What is memoization? Under what circumstances can it be useful and how can it be used? (If possible, illustrate with a simple example)
31
Memoization is to use a cache table to avoid having to recalculate the value of a function more than once. A classic example is a naive implementation of the Fibonacci function:
function fib(n){
if(n == 0 || n == 1){
return 1;
}else{
return fib(n-1) + fib(n-2);
}
}
This naive implementation takes exponential time because we recalculate the lower values of fib
often.
fib(5) =
(fib(4) + fib(3)) =
((fib(3) + fib(2)) + fib(3)) = -- fib(3) é calculado 2 vezes...
(((fib(2) + fib(1)) + fib(2)) + (fib(2) + fib(1))) = -- fib(2) é calculado 3 vezes...
...
A direct way to solve the problem is to store the results already calculated in a table. So we spend more memory but at least finish the bill faster:
var computed_fibs = [];
function fib_memo(n)
if(!computed_fibs[n]){
computed_fibs[n] = fib(n);
}
return computed_fibs[n];
}
function fib(n){
if(n == 0 || n == 1){
return 1;
}else{
return fib_memo(n-1) + fib_memo(n-2);
}
}
25
memoization is a term used by Donald Michie in 1968 and is derived from the Latin word memorandum (to be remembered). Practically speaking:
It is the result cache of a function, based on the input parameters.
When calling a function with certain parameters, if the requested result is already in the cache, returns it, instead of calculating/doing it all over again.
I made a simple implementation here.
Example:
var resultados = new Dictionary<string,double>();
double Soma(double A, double B)
{
var key = A + "[+]" + B; // Os parâmetros vão aqui, com um separador distinto.
// Verifica se já sabemos este resultado
if(resultados.ContainsKey(key)) return resultados[key];
Thread.Sleep(5000); // Processamento pesado :)
var resultado = A + B; // Calculando A + B ...
resultados.Add(key, resultado); // Adiciona resultado destes parâmetros no cache
return resultado; // Retorna resultado A + B
}
Soma(3, 4); // Demora.
Soma(3, 4); // Retorna rápido o resultado, pois usou o cache.
Browser other questions tagged algorithm terminology
You are not signed in. Login or sign up in order to post.