35

O que é memoization? Em quais circunstâncias pode ser útil e como utilizar? (Se possível, ilustrar com um exemplo simples)

2 Respostas 2

34

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);
    }
}
0
27

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.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .