YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Portuguese, Brazilian subtitles

← 04-07 Memoization

04-07 Memoization

Get Embed Code
3 Languages

Subtitles translated from English Showing Revision 4 created 02/25/2013 by Lucilia Figueiredo.

  1. Você deve ter notado que aqui à direita eu fiz uma tabela,
  2. para explicar como Fibonacci funciona.
  3. Vamos usar esse mesmo tipo de tabela para tornar fiibo mais rápida,
  4. evitando repetir um bocado de trabalho.
  5. Nosso plano para isso é chamado `memoization'.
  6. É como memorização, mas sem o r.
  7. Aqui, eu tentei desenhar 2 `memos': um memorando corporativo e estas notinha amarelas,
  8. que se usa algumas vezes para escrever algum lembrete para si mesmo.
  9. Um memo, em Inglês, é simplesmente um documento, um pequeno documento,escrito --
  10. -- um memorando.
  11. Porque isso nos interessa?
  12. Bem, acontece que nossa atual implementação de Fibonacci é super lenta.
  13. Vou tentar provar isso para você.
  14. Vejamos quanto tempo é gasto para 100 tentativas de calcular fibo(20) --
  15. mais ou menos 0.3 seg.
  16. Vamos aumentar um pouco, para fibo(24) --
  17. deve gastar muito mais, né?
  18. Oh! Muito muito mais -- de 0.3 seg para 1.75 seg.
  19. cresceu um bocado!
  20. Vamos ver para fibo(25) -- oh! quase dobrou:
  21. temos agora 2.8 seg!
  22. De fato, temos motivo para acreditar, com base em estudos do comportamento humano,
  23. que se uma página web gasta mais que 6 seg para carregar,
  24. você vai comprar seu produto em algum outro site.
  25. Portanto, estamos usando uma grande fração deste tempo, apenas para computar
  26. fibo(25).
  27. E se você pensar nas árvores que eu desenhei antes, isso não será uma surpresa.
  28. Se aumentamos n de 1, quase dobramos o trabalho em cada passo.
  29. Isso é inadimissível -- precisamos de algo mais rápido.
  30. Nossa solução é escrever, em uma tabela -- um pequeno memo -- para nos lembramos.
  31. Vou construir uma tabela mapeando n a fibo(n) --
  32. 1,1,2,3,5,8 --
  33. e quando eu estiver calculando isso, eu não tenho que fazer muito trabalho.
  34. Suponha que eu queira calcular fibo(6).
  35. Eu posso simplesmente olhar na tabela e reusar meu trabalho anterior.
  36. Eu não tenho que recalcular fibo(5) -- já tenho isso aqui.
  37. Apenas somo o valor dessas 2 células e obtenho a resposta.
  38. Essa é a nossa idéia para tornar fibo muito mais rápida.
  39. É chamada de `memoization' (memorização).
  40. Podemos implementar nossa tabela, em Python, como um dicionário,
  41. apenas preenchendo os números, à medida que os calculamos.
  42. Portanto, eu começo com um dicionário vazio, atribuo valores às entradas do dicionário,
  43. e verifico se algo, como no caso de 6, já está calculado.
  44. E se estiver, eu imprimo o resultado.
  45. Isso será super necessário agora, e talvez não tenha sido antes.
  46. Uma das idéias chave de memorização é verificar se o trabalho já foi feito,
  47. e anotá-lo.
  48. Se já foi feito, ótimo! Você pode simplesmente reutilizá-lo.
  49. Se não, você tem que fazer o cálculo uma primeira vez.