7 Jan 2009 acs   » (Journeyer)

Mais Fibonacci: Usando Memoize com map em C++


Há alguns dias atrás, novamente em uma discussão em um dos coffeetime que normalmente ocorrem na empresa, que por sinal são muito produtivas, estávamos eu e mais dois amigos programadores discutindo sobre a técnica de tail recursion, que ajuda bastante na otimização de funções recursivas, porem, estava matutando e me lembrei que existe uma outra técnica, também muito utilizada, principalmente em programas que exigem recursividade e implementam Programação Dinâmica, que é a técnica do “Memoization”.

Mais, resumindo, o que seria esse tal de memoization??? como a própria palavra diz, memoize e um termo que deriva do latim memorandum, ou seja, relembrando, exatamente como essa técnica faz, ela armazena em cache as chamadas de função que são repetidas em varias vezes, economizando assim um tempo precioso no acesso dessas informações.

Exemplos clássicos de demonstração dessa técnica são as implementações recursivas de Fibonacci e calculo de fatorial, no nosso caso, iremos utilizar Fibonacci, por estarmos mais familiarizados com essa função nesse humilde blog.

Suponha, que temos uma implementação recursiva de Fibonacci:

int fib( int n )
{
   if ( n <2 )
     return 1;
   else
     return fib( n - 1 ) + fib( n - 2 );
}

Implementaremos o memoization nessa função, utilizando uma implementação com map da seguinte maneira:

std::map<int,int> resultado;
int fib( int n )
{
  if ( n == 0 || n == 1 )
    return 1;
  std::hash_map<int,int>::iterator it = resultado.find( n );
  if ( it != resultado.end() )
    return it.second;
  else
    return resultado[ n ] = fib( n -1 ) + fib( n - 2 );
}

Ou seja, na primeira vez que esse código for executado, por exemplo, para um fib(4), ele vai ter que calcular respectivamente o fib(2) e fib(3), porem, quando eu chamar um fib(5), como os resultados anteriores ja estarão armazenados no map e o valor será retornado sem nenhum calculo adicional, e com isso, teremos um bom ganho no tempo de execução.

Esse pode ser um recurso muito útil quando estamos lidando com algoritmos que lidam com recursividade, onde a programação dinâmica pode ser aplicada, como por exemplo, uma multiplicação de cadeia de matrizes, um alinhamento de sequência ou ate mesmo um algoritmo de otimização para busca em arvores binárias.

Syndicated 2008-01-23 16:49:13 from Jumpi's Notepad

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!