Pular para o conteúdo
Even3

Como usar cache e dicionários para otimizar Fibonacci em Python

Trecho de 2 min de Python e problemas matemáticos desafiadores, gravado no evento PyMat 2021 - Python para Matemática e Além.

Assistir à gravação completaNo Even3 Conteúdos · 1 h 58 min

Sobre este trecho

Descubra como a técnica de cache com dicionários evita o recálculo exponencial na sequência de Fibonacci, tornando o acesso a termos anteriores muito mais rápido.

Vai de a da gravação.

O que é dito neste trecho

Ora, quando chega no f 12 eu já tenho calculado o f 11. Então já tenho calculado também o f 10, eu preciso deles dois para saber quem é o f 12. Tá certo? Então por que motivos eu vou ter que fazer toda a recorrência novamente? Então a gente vai usar o modelo de cache. Que é o modelo de cache? Você vai guardar todo mundo que você já eh que você vai que você já usou. Uma forma de fazer isso é o já dicionários, pessoal, dicionários. Que são esses dicionários? Eles são eh eles são obtidos a partir de chaves, tá certo? E você é uma uma uma questão de chave e valor, chave e valor, chave e valor. A chave sempre o primeiro termo. Vou botar aqui zero e o valor de zero vai ser zero também. No caso aqui vai ser um e o valor aqui também vai ser um, certo? Agora isso aí pode ser qualquer coisa, tá bom? A diferença disso aí é porque no dicionário você pode botar como chave uma string, tá certo? Então facilita, né? Se você quiser fazer, por exemplo, porque o nome é dicionário, né? Porque você não guarda a posição. Não importa a ordem aí, se começa zero ou um, não. É diferente de lista, que você bota um número, um valor na determinada posição. Já no dicionário isso não acontece. Você tem um acesso a essa estrutura de dados através da da da chave. Se eu disser aqui, eu vou pegar aqui uma um dicionário com os preços do dicionário dos preços da Tá acontecendo alguma coisa aqui? Não, né? Pronto, dicionário dos preços de de uma frutaria. Então vou tá banana eh R$10, maçã R$5 e assim vai. Eu quero acessar esse valor dessa banana. Eu vou lá, boto a string banana e acesso. Certo? Não importa se banana foi colocado no dicionário em primeiro, segundo, em qualquer outro lugar. Dessa forma ele é mais rápido de acesso, certo?

Outros trechos deste conteúdo