Analisando computacionalmente a Sequência de Fibonacci
Usando Matemática para medir, otimizar e criticar diferentes algoritmos em Python
Esse artigo irá mostrar três diferentes algoritmos para se encontrar o n-ésimo valor da sequência de Fibonacci — incluindo uma forma sem loops para percorrer toda a sequência. Serão estudados seus desempenhos e limitações computacionais. Ao final, é feita uma reflexão sobre a metodologia usada, discussão de trade-offs e uma proposta de solução ao problema de otimização precoce. O objetivo geral é demonstrar uma união entre técnica e ciência.
Os algoritmos serão escritos em Python — mas não se preocupe se desconhecer essa linguagem, porque o código estará bem agnóstico e legível. E noções básicas de Matemática talvez ajudem.
E o que é a Fibonacci?
Com certeza você já deve ter visto essa sequência na natureza (ou até em piadas na Internet), mesmo sem conhecê-la pelo nome. Resumo: é uma lista infinita de números, em que cada um de seus valores é o resultado da soma dos dois anteriores. Isso pode parecer confuso à primeira vista, mas olhando na prática fica mais fácil digerir:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Note que o último número aí escrito, 89, está lá porque o que vem antes dele são 55 e 34, e sabemos que 55+34=89. Cada valor recorre aos seus antecessores para se definir. E esse padrão se repete pra sempre, com exceção dos primeiros 0 e 1 que são “independentes”, isto é, são os “casos base” dessa sequência.
Veja mais uma representação visual desse padrão:
E a presença desse padrão nos mais inusitados locais:
Definição empírica
É possível organizar essa “lista infinita” de números Fibonacci usando uma notação de número ordinal. Um bom início é nomear os dois casos base 0 de zerésimo (0º) e 1 como primeiro (1º). Ficaria assim:
0º= 0,
1º= 1.
Consequentemente, os números seguintes:
2º= 1,
3º= 2,
4º= 3,
5º= 5,
6º= 8, (…)
Observe que o 6º é resultado da soma entre o 5ºe o 4º. Não importa qual seja o enésimo (nº), ele será a soma do que vier antes dele (n-1)º e o que vier antes disso (n-1-1)º. Generalizando isso em variáveis:
nº = (n-1)º + (n-2)º
Por exemplo, para encontrar o terceiro se tem n=3, isto é:
3º = (3–1)º + (3–2)º
3º = 2º + 1º
3º = 1 + 1
3º = 2
E assim o terceiro número da Fibonacci é igual a 2.
Essa é uma maneira eficaz de achar qualquer nº (enésimo ou n-ésimo) termo da sequência.
Definição analítica
Esse padrão que observamos empiricamente é chamado relação de recorrência. A notação que usamos na Matemática Discreta para escrevê-lo é semelhante à de qualquer outra função matemática (aquelas com domínio, imagem e tudo mais):
f(0) = 0;
f(1) = 1;
f(n) = f(n-1) + f(n-2), para qualquer natural n > 1.
Lendo assim, o valor de f(n) seria o tal n-ésimo termo, não importando qual o argumento n, desde que n seja número natural.
Implementando os três algoritmos
Para os códigos, iremos assumir que os casos bases são f(1)=1 e f(2)=1. Apesar disso, não haverá diferença alguma nos valores da sequência.
Usando recursão
Aquela relação de recorrência é traduzida para uma função recursiva — isto é, uma função que “chama a si própria” — sem muito esforço. Uma possivel definição da função Fibonacci em Python seria:
def f(n: int):
if n == 1:
return 1
if n == 2:
return 1
else:
return f(n-1) + f(n-2)Havendo compreendido o raciocínio matemático por trás disso, essa solução é muito mais limpa e legível, se encaixa muito bem em Python. Observe que, da forma como está escrito aí, cada chamada da função irá chamar outras duas funções, o que pode ser um problema.
Usando iteração
Um algoritmo iterativo seria basicamente aquele que possui a estrutura de repetição, como o for. Esta seria a forma mais “normal” de se programar um comportamento repetitivo.
def f(n: int):
ultimo = 1
penultimo = 1 if n == 1:
return penultimo elif n == 2:
return ultimo else:
atual = 0
for i in range(2, n):
atual = ultimo + penultimo
penultimo = ultimo
ultimo = atual
return atual
Uma rápida legenda “pythônica”: a linha
for i in range(2, n)pode ser lida como: “faça i contar de 2 até n-1, extremidades inclusas” ou, como é na maioria das linguagens populares,for (i = 2; i < n; i++).
À primeira vista, parece que ficou mais robusto e longo em relação ao recursivo.
Usando matemática
Esta terceira forma é a mais “mágica” de todas, sem necessidade de repetições nem recursões. Contemple a forma fechada da Sequência de Fibonacci:
O que em Python seria:
from math import sqrt, powdef f(n):
raiz5 = sqrt(5)
return int((1/raiz5)*(pow((1+raiz5)/2,n)-pow((1-raiz5)/2,n))
No Python, as funções
sqrtepowdo módulomathsão, respectivamente, funções de raíz quadrada e potenciação.
Apesar da legibilidade do código estar visivelmente degradada e ser muito difícil de customizar futuramente esse algoritmo, essa versão é extremamente previsível, fácil de testar, veloz e possível de ser comprovada matematicamente.
A fórmula assusta, mas passado o susto inicial, já podemos visualizar alguns “problemas”:
- o tipo decimal float tem problemas de precisão que atrapalharão a eficácia;
- a presença de um número irracional é um perigo à eficácia;
- os cálculos de raíz quadrada e potenciação talvez atrapalhem a eficiência.
Apesar disso, a acurácia desse algoritmo continua aceitável. Até a precisão se tornar um problema, o tamanho do tipo inteiro na memória já teria estourado antes.
A técnica da Matemática Discreta que usei para chegar a essa fórmula fechada serve para outras relações de recorrência e está disponível no meu Github em passo a passo: https://github.com/Mazuh/MyNotebook-Math/blob/master/files/discrete/fibonacci.pdf
Comparando as execuções
Colhendo dados
Os três códigos acima foram executados e seus tempos de duração mensurados diante do interpretador Python 3.5 com garbage collector desativado.
Os scripts usados para esses testes também estão no meu Github: https://github.com/Mazuh/Fibonacci
As funções foram testadas para vários n diferentes, de 1 até 40. E, para cada possibilidade de n, as funções foram executadas 1 milhão de vezes na minha máquina pessoal. Os desempenhos (em segundos) estão dispostos no gráfico abaixo:
No gráfico, quanto mais a curva subir, mais trabalho o código teve para rodar— isto é, pior foi o desempenho. Observam-se de início: deformações no início das linhas; uma delas fez uma linha reta crescente de trabalho, outra fez uma linha reta horizontal constante e outra cresceu estranhamente muito rápido.
Contrariando uma intuição inexperiente, o código pequeno e legível (o recursivo) apresentou um resultado bem pior do que os outros mais verbosos e complicados.
Observando a linha constante da forma fechada
De longe foi o algoritmo mais otimizado. E a linha de desempenho permanecerá naquela altura sempre, como em uma função constante. Porque independentemente de qual seja o valor de n, a quantidade de operações matemáticas realizadas será sempre a mesma.
Aparentemente o interpretador Python tomou várias decisões legais baseado em propriedades matemáticas.
Note que as exponenciações tiveram um desempenho bem escalável, isto é, mesmo com o n aumentando, o trabalho realizado pela função durante esse domínio analisado não mudou.
Outro sinal que o interpretador deixou foi a perturbação no início do gráfico. Não escrevemos nenhuma condicional para checar os casos base nesse algoritmo: só tem uma linha de cálculo lá. Mas no caso base n=1, há um valor mínimo na imagem, porque é sabido que elevar um número a 1 não faz nada (como somar um valor a 0, ou seja, não altera o resultado). Já o caso n=2 produz cálculos de expoente 2, e ele também é otimizado, porque esse tipo de cálculo pode ser feito em base binária com operadores bitwise; o hardware trabalha com valores binários e isso fica mais fácil para ele.
Entendendo a linha crescente do algoritmo iterativo
O gráfico de onerosidade da versão iterativa (aquela com repetição por “for”) virou uma linha afim, e é possível confirmar isso analiticamente.
Há uma deformação no início desse gráfico também. Mas, diferente do código recursivo, aqui ela está explícita: está escrito de fato uma condicional para cada caso base.
De resto, a função é só um loop, e esse loop repete 4 operações a cada iteração: uma soma e três atribuições de variáveis, aparentemente. E essa repetição ocorrerá n-2 vezes. Logo, o desempenho desse algoritmo está em função de n e realizará 4*(n-2) operações, o que por propriedade distributiva é igual a 4n-8. Notamos que isso é uma função de primeiro grau, cujo gráfico será uma linha reta crescente.
No entanto, dizer que esse algoritmo iterativo de Fibonacci realiza 4n-8 operações não é exato, porque implicitamente o interpretador irá alterar bastante a quantidade de operações até chegar ao nível de máquina. Mas é suficiente para afirmar que esse algoritmo tem complexidade linear — devido ao formato que o gráfico de trabalho tende a assumir. Quanto maior o valor de n, pior o desempenho, mas de forma proporcional.
Em geral, algoritmos iterativos se comportam linearmente, não só o de Fibonacci. À exceção dos loops que possuem outros loops aninhados dentro de si, aqueles bagunçados por instruções de controle e códigos assíncronos, por exemplo, mas isso é outra história.
Investigando o problema do código recursivo
O tempo necessário para executar a forma recursiva virou uma linha exponencial — e quanto mais o valor de n aumenta, o desempenho se deteriorará em uma velocidade bem desproporcional.
Lendo bem o código da recursiva, cada chamada da função irá chamar outras duas. Dessa forma, na primeira chamada haverão 2 escopos sendo invocados, acumulativamente na segunda haverão 4 e depois 8; o padrão é de uma potenciação de base 2 com expoente n, ou seja, aproximadamente 2^n operações. E este é o principal sufoco do nosso algoritmo recursivo, mas há outros problemas relacionados.
Um desses problemas menores é que é “natural” que recursão seja mais onerosa. O código de máquina gerado por uma recursão é um pouco mais complexo. E a operação de chamar funções recursivamente tem uma “profundidade” limitada: sempre que a função chamar a si própria, é reservado um espaço para ela em uma pilha de memória. Exceder o espaço dessa pilha seria um stack overflow.
Talvez alguém conjecture que essa lentidão extrema é inerente a todo algoritmo recursivo. Mas isso não é sempre verdade, porque dependendo da linguagem e do código recursivo tal comportamento não se repete com a mesma intensidade. Restaria a hipótese de que há algo “errado” com o Python, e isso é verdade de certa forma. O interpretador Python não fornece suporte nativo à otimização de recursão por cauda e seu autor Guido prefere assim.
Otimização de recursão por cauda seria um recurso para fazer o algoritmo recursivo produzir códigos de máquina semelhantes aos do iterativo. Isso uniria a boa legibilidade da recursão à eficiência da iteração.
Portanto, vários foram os fatores que contribuiram para essa função dar “errado”, mas ela serve para mostrar que legibilidade e simplicidade podem esconder coisas terríveis se não tivermos uma visão holística da programação.
Conclusões
Finalmente, algumas coisas podem ser inferidas a partir desses testes e análises.
Quantidade de linhas não é fator determinístico
Foi provado na prática que mesmo códigos bonitos e curtos podem ser desastrosos em termos de performance. As aparências enganam.
Para análise de desempenho, deve ser mais levado em conta o algoritmo em si, seu compilador e seu ambiente de execução, não só o que o está escrito no código de alto nível. É preciso se tomar cuidado com abstrações demais, porque elas são sensíveis a falhas desconhecidas.
Em suma, algo verboso não necessariamente é ruim; e uma escrita bem feita não equivale a eficiência. No fim, cabe ao programador decidir as consequências de suas implementações, porque algo ser lento também não necessariamente é ruim. O importante é que o desenvolvedor esteja ciente das decisões que tomou.
Metodologia científica é muito útil para programadores
Neste artigo, produzimos diferentes resultados e discussões através de alguns passos lógicos: experimentamos fenômenos controladamente, elucidamos fatos, depois testamos hipóteses e tiramos conclusões para gerar “novos fatos”. E isso tudo mesmo com escopo simplista e usando um objeto bem “pedagógico” como a Sequência de Fibonacci.
O método científico auxilia um desenvolvedor a provar com mais exatidão seu raciocínio, saber organizar melhor suas soluções e tentar buscar respostas para além do código a sua frente.
Dito isso, não subestime o âmbito científico só por julgar já saber o suficiente a partir de documentações e vídeos. É como, por exemplo, saber ler e escrever, para depois ser capaz de interpretar, criticar e criar gêneros textuais para melhorar o que você já lê e escreve. É uma ferramenta extra ao seu arsenal.
Otimização precoce é um problema
A prática leviana de otimização é problemática. Envolve toda uma questão de decisões: saber quando e por que perder aqui para vencer acolá.
Vejamos um cenário comum: assumindo que você tenha escrito a primeira versão do seu algoritmo de Fibonacci de forma recursiva ou iterativa; valeria a pena tentar criar uma nova solução mais eficiente como a forma fechada? Você precisaria recorrer a valores como f(10000) frequentemente? Seu serviço está lento e aquela parte talvez seja o problema?
Uma dica muito legal seria não tomar decisões baseadas em “achismo” nem requinte exagerado, mas em objetividade: mensure, faça benchmarking, prove que aquilo precisa ser otimizado. Seja racional e produtivo, não somente ocupado.
Matemática não é inútil
A Sequência de Fibonacci foi um exemplo bem didático, porém as técnicas usadas para construir os algoritmos são muito comuns no dia a dia de todo desenvolvedor. Computador é, por definição, uma máquina de calcular, e ter noções fundamentais de Matemática e hardware são úteis para ampliar a visão sobre o trabalho que o programador está fazendo, o que inconscientemente pode incrementar a confiança dele sobre o que está sendo feito.
“Como matemáticos, os cientistas da Computação usam linguagens formais para denotar ideias; como engenheiros, eles projetam coisas unindo componentes a sistemas e avaliando decisões; como cientistas, eles observam o comportamento de sistemas complexos, formulam hipóteses e testam prognósticos.” (How to Think Like a Computer Scientist: Learning with Python)
