Jumpi’s Notepad

My annotations about the life, universe and everything!!! ;)

Mais Fibonacci: Usando Memoize com map em C++

with one comment

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.

About these ads

Written by jumpi

January 23, 2008 at 4:49 pm

One Response

Subscribe to comments with RSS.

  1. Legal. No início até achei que vc tivesse se esquecido de um *r* em memoization. Depois vi que não… Post interessante.

    0xc0de

    May 22, 2009 at 12:44 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: