O que é memoization? Em quais circunstâncias pode ser útil e como utilizar? (Se possível, ilustrar com um exemplo simples)
2 Respostas
Memoization é usar uma tabela de cache para evitar ter que recalcular o valor de uma função mais de uma vez. Um exemplo clássico é uma implementação ingênua da função de Fibonacci:
function fib(n){
if(n == 0 || n == 1){
return 1;
}else{
return fib(n-1) + fib(n-2);
}
}
Essa implementação ingênua gasta tempo exponencial pois recalculamos os valores menores de fib
muitas vezes.
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...
...
Uma maneira direta de resolver o problema é guardando os resultados já calculados em uma tabela. Assim nós gastamos mais memória mas pelo menos terminamos a conta mais rápido:
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);
}
}
memoization é um termo usado por Donald Michie em 1968 e é derivado da palavra Latina memorandum (ser lembrado). Em termos práticos:
É o cache do resultado de uma função, baseado nos parâmetros de entrada.
Ao chamar uma função com determinados parâmetros, se o resultado pedido já estiver no cache, retorna ele, ao invés de calcular/fazer tudo novamente.
Fiz aqui uma simples implementação.
Exemplo:
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.