What is a memoization?

Question

What is memoization? Under what circumstances can it be useful and how can it be used? (If possible, illustrate with a simple example)

Answer 1

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

Answer 2

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.