Estava apreciando hoje de manhã um post do Felipe Tonello: Analisando Número de Fibonacci e Recursividade. É um bom artigo sobre aquelas coisas que alguns podem ter visto na faculdade e são sempre uteis: matemática, analise de algoritmos e um pouco de mente aberta.
Imediatamente tratei de testar a velocidade dos dois algoritmos propostos usando AWK (que, por ser interpretado, pode revelar melhor as nuances entre as abordagens). Algoritmos recursivos são interessantes, principalmente quando trabalhamos com linguagens funcionais, porém algumas formas tem um custo computacional muito alto e o calculo de Fibonacci é um exemplo perfeito: para cada termo eu preciso calcular os dois termos anteriores e, então, soma-los, e isso cresce geométricamente, consumindo memória e processamento, sem falar que tenho muita repetição de código desnecessária.
A tecnica de programação dinâmica apresentada cria um cache de resultados, dessa forma evito boa parte do trabalho extra, veja o resultado:
Fibonacci(36) pelo algoritmo recursao simples:14930352 usando 48315633 iteracoes real 0m51.961s user 0m23.881s sys 0m0.012s Fibonacci(36) pelo algoritmo programacao dinamica:14930352 usando 71 iteracoes real 0m0.002s user 0m0.000s sys 0m0.000s
Usando programação dinâmica eu uso muito menos de 1% do processamento necessário pela forma recursiva tradicional. Parece ótimo, não? Depende, pois eu apenas afastei o problema: ao calcular termos de alta ordem eu terei o mesmo problema, afinal o algoritmo é O[n].
Lembrei de um post do Ronaldo Melo Ferraz, Conceitos de Programação: Tail Recursion enquando estava testando os algoritmos em Erlang e encontrei esta implementação. A adaptação para awk é tranquila e o teste mostrou este resultado:
Fibonacci(36) pelo algoritmo programacao dinamica:14930352 usando 71 iteracoes real 0m0.002s user 0m0.000s sys 0m0.000s Fibonacci(36) pelo algoritmo tail recursion:14930352 usando 38 iteracoes real 0m0.001s user 0m0.000s sys 0m0.004s
Um resultado ainda mais interessante, pois eu consigo obter o valor do termo com um pouco mais da metade das iterações do que usando programação dinâmica (sem onerar a memória com o cache dos resultados).
Esta analise é muito superficial, a ideia é apenas despertar a curiosidade sobre estes tópicos.
O codigo fonte utilizado nesse benchmark:
function Fib_normal(N) {
return (N > 1)? Fib_normal(N-1) + Fib_normal(N-2) : N
}
function Fib_dinamic(N) {
if (!m[N]) m[N] = (N > 1)? Fib_dinamic(N-1) + Fib_dinamic(N-2) : N
return m[N]
}
function Fib(N) { return Fib_tr(N,0,1); }
function Fib_tr(I,R,N){
return (I==0)? R : Fib_tr(I-1,N,R+N)
}
