Fibbonacci com Memoization

Fibbonacci com Memoization - O(n)

Publicado por Daniel Gimenes 27/05/2009

[ Hits: 6.549 ]

Download fibonacci.c

0 0

Denuncie Favoritos Indicar

Visto que rolou uma brincadeira de otimização do código que encontra um número de fibonacci aqui (http://www.vivaolinux.com.br/script/Sequencia-fibonacci-com-35-linhas-e-for), resolvi mostrar uma técnica legal para se ter um desempenho muito superior.

A brincadeira do pessoal era em relação ao menor número de linhas. Porém, o que quero mostrar aqui é o desempenho de execução.

Vejam a diferença:

Código cedido pelo thiagodorneles com algumas modificações:

#include<stdio.h>

long int fibo(int n)
{
   return ((n<2)?1:(fibo(n-2)+fibo(n-1)));
}

int main(int argc, char **argv)
{
   int v = atoi(argv[1], 10);
   long int r = 0;
   r = fibo(v);
   printf("Resultado fibonacci: %ld\n",r);
}

Comparação de tempo de execução entre o meu código e o do Thiago:

dang@server:~/fibo$ time ./fibo_daniel 40
Fibonacci[40] = 165580141

real    0m0.025s
user    0m0.000s
sys     0m0.024s
dang@server:~/fibo$ time ./fibo_thiago 40
Resultado fibonacci: 165580141

real    0m5.548s
user    0m5.380s
sys     0m0.028s

Quem quiser fazer o teste, fique a vontade.

A idéia da técnica de memorization é guardar os valores já calculados para evitar recálculo. Este é uma das bases da programação dinâmica. ;)

Bom estudo a todos,
Daniel

Esconder código-fonte

#include <stdio.h>

#define MAX 512
int v[MAX];

int fibonacci(int n)
{
   if (n < 2)
      return 1;
   if (v[n] != 0)
      return v[n];
   return v[n] = fibonacci(n-1) + fibonacci(n-2);
}

int main(int argc, char **argv)
{
   int n = atoi(argv[1], 10);
   memset(v, 0, sizeof(int)*n);
   printf("Fibonacci[%d] = %d\n", n, fibonacci(n));
   return 0;
}

Scripts recomendados

POGRAMA EM C REGISTRO DE CADASTRO ALTERAR E REMOVER CLIENTES PRODUTOS

jogo Sokoban (com gráficos)

Algoritmo de Fatoração de Fermat (FFA) em C

Jogo da velha em C

Função "Partição de Inteiros" Recursiva COM Tabela Estática em C

Comentários

[1] Comentário enviado por danielgimenes em 27/05/2009 - 01:10h

O nome da técnica é Memoization... foi mal pessoal.

0 0

[2] Comentário enviado por Teixeira em 27/05/2009 - 08:45h

Boa dica, Daniel. É sempre importante saber que existem várias maneiras de se conseguir os mesmos resultados.
Alguns resultados são mais rápidos, outros mais seguros, outros conseguem ser tão rápidos quanto seguros, outros são melhor implementados em outra linguagem, e assim por diante.
Quem resolve dedicar-se a programação deve estar atento a técnicas específicas, e às características de cada linguagem, visando obter o melhor desempenho na resolução dos problemas.
As linguagens modernas tendem a trazer-nos uma certa acomodação mental, através do uso de módulos preconfigurados.
Nada de errado com isso; Porém se nos deixarmos acomodar, nosso raciocínio poderá ficar bastante bitolado, o que não é nada bom.

0 0

[3] Comentário enviado por elgio em 27/05/2009 - 09:18h

Interessante, mas me permita minha contribuição.

Complexidade é uma coisa legal. A serie de fibonacci aumenta o tempo de execução de acordo com o tamanho do elemento. No teu caso fizeste a serie de forma iterativa, ou seja, SEM RECURSÃO. recursividade é um LIXO para este tipo de coisa pois gasta muito tempo e pode ESTOURAR a pilha.

Mas tem uma forma MATEMÁTICA, com um ÚNICO PASSO que permite chegar a qualquer elemento da série (Algoritmos, Teoria e Prática, de Thomas H. Cormem).

A formula é meio esdrúxula e pode ter erro de precisão por conta dos doubles (raiz quadrada) mas FUNCIONA.
#include <stdio.h>
#include <math.h>
unsigned long int fibo(unsigned long int n)
{
long double s=sqrtl(5);
long double a1, a2;

if (n<=1){
return(n);
}

a1 = powl( (1+s)/2.0 ,n);
a2 = powl( (1-s)/2.0 ,n);

return ( (a1 - a2)/s + 0.5);
}

Só que neste caso, ao contrário do teu, o primeiro elemento é o posição 1 e não ZERO. Então o teu FIBO 40, aqui tem que ser passado 41:

elgio@didake:~/ulbra/Disciplinas/estrutura2/src> time ./fiboMAT 41
O elemento 41 da serie eh 165580141

real 0m0.003s
user 0m0.000s
sys 0m0.008s
elgio@didake:~/ulbra/Disciplinas/estrutura2/src>

MAIS UMA VEZ, saliento que por causa do uso de ponto flutuante e da perda de precisão, pode ter diferenças no resultado. Mas estamos falando de conceitos matemáticos, e tem uma forma de calcular qualquer elemento da série sem for ou recursividade (pois na matemática tu não precisas perder a precisão do raiz quadrada). Para melhorar muito, eu uso long double, que se estiver em um compilador de 64 bits será de 16 BYTES (128 bits) de tamanho :-O e um long int de 8 BYTES (64 bits).

Mas acredito (a ser testado) que em um simples compilador de 32 bits não se perderá precisão para elementos pequenos (no meu, o processo matemático perde precisão no 85):

elgio@didake:~/ulbra/Disciplinas/estrutura2/src> for A in `seq 81 90`; do ./fiboMAT $A; ./fiboIT $A;echo ;done
O elemento 81 da serie eh 37889062373143906
O elemento 81 da serie eh 37889062373143906

O elemento 82 da serie eh 61305790721611591
O elemento 82 da serie eh 61305790721611591

O elemento 83 da serie eh 99194853094755497
O elemento 83 da serie eh 99194853094755497

O elemento 84 da serie eh 160500643816367088
O elemento 84 da serie eh 160500643816367088

O elemento 85 da serie eh 259695496911122586
O elemento 85 da serie eh 259695496911122585

O elemento 86 da serie eh 420196140727489674
O elemento 86 da serie eh 420196140727489673

O elemento 87 da serie eh 679891637638612260
O elemento 87 da serie eh 679891637638612258

O elemento 88 da serie eh 1100087778366101934
O elemento 88 da serie eh 1100087778366101931

O elemento 89 da serie eh 1779979416004714193
O elemento 89 da serie eh 1779979416004714189

O elemento 90 da serie eh 2880067194370816127
O elemento 90 da serie eh 2880067194370816120

0 0

[4] Comentário enviado por elgio em 27/05/2009 - 09:21h

Outra contribuição.

Eu mudaria de:

#define MAX 512
int v[MAX];

int fibonacci(int n)
{
if (n < 2)
return 1;
...

Para:
#define MAX 512

int fibonacci(int n)
{
static int v[MAX];

if (n < 2)
return 1;
...

MOTIVO: variáveis globais não é nada legal de ser usado!! Efeito colateral.

0 0