Lucas Gabriel G. dos Santos - Engenheiro de Computação
Realizei a implementação de dois exemplos de código do livro "Problemas Clássicos de Ciências de Computação com Python". Nestes exemplos são apontados problemas decorrentes da quantidade de chamadas recursivas e como isto pode comprometer o desempenho da aplicação.
No arquivo fib-memo.py fiz uso da estrutura de dicionário para armazenar passos já concluídos de casos já resolvidos em etapas anteriores. Um exemplo de como a memoização pode reduzir a quantidade de chamadas recursivas. Exemplo de saída com fibonacci.py:
n = 6
Exemplo de saída com fib-memo.py:
n = 5 e n = 20
❯ python fib-memo.py 5 6765
{
"0": 0,
"1": 1,
"2": 1,
"3": 2,
"4": 3,
"5": 5,
"6": 8,
"7": 13,
"8": 21,
"9": 34,
"10": 55,
"11": 89,
"12": 144,
"13": 233,
"14": 377,
"15": 610,
"16": 987,
"17": 1597,
"18": 2584,
"19": 4181,
"20": 6765
}
Como realizei a implementação do método de fibonacci com memoização e com o uso de cache optei por ter um módulo próprio com as funções, por hora pertencentes a arquivo distintos.
Para criar um módulo é necessário adicionar uma nova pasta ao projeto com o arquivo init.py.
para importar de um módulo pode-se fazer:
from nome_do_modulo.nome_do_arquivo import nome_da_func
Demais detalhes e otimizações poderãos ser feitos futuramente.
Árvores são estruturas muito práticas para algumas classes de problemas. Pretendo abordar mais deste assunto a partir deste repositório, planejando atualizações semanais.