English subtitles

← 04-07 Memoization

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 05/06/2012 by Amara Bot.

  1. You might have noticed that up here on the right, I made a very simple chart
  2. to try and explain how Fibonacci behaves to myself.
  3. We're going to use this same sort of chart to make Fibonacci much faster
  4. by voiding repeating a lot of work.
  5. Our official plan for this is going to be called Memoization.
  6. It's just like memorization, but missing an r.
  7. Here I've tried to draw 2 memos: a corporate memo and those yellow sticky notes
  8. you sometimes see, where you could write a little memo to yourself.
  9. A memo in English is just a document, a small document, that's written down--
  10. memorandom.
  11. Why bother with this?
  12. Well, it's going to turn out that our current implementation of Fibonacci is super slow.
  13. Let me try to prove that to you.
  14. So let's see how long it takes to do 100 trials of the 20th Fibonacci number--
  15. about .3 seconds.
  16. Let's up that a bit to the 24th Fibonacci number--
  17. should take not that much longer, right?
  18. Oh! Significantly longer, from .3 seconds to 1.75 seconds.
  19. We went up a huge amount.
  20. Let's go up to the 25th Fibonacci number--oh! We almost doubled.
  21. We're now at about 2.8 seconds.
  22. In fact, we have reason to believe based on human studies
  23. that if a webpage takes longer than 6 seconds to get back to you,
  24. you go somewhere else and buy something different online.
  25. So we're already using up a huge fraction of that budjet just to compute
  26. the 25th Fibonacci number.
  27. And if you think about those trees I drew before, this is unsurprising.
  28. If we increase the number by 1, we almost double the work at each step.
  29. So this is untenable. We need something faster.
  30. Our solution we'll be to write it down in a chart, or a little memo, to ourselves.
  31. I'll just make a table mapping N to the value of Fibonacci of N.
  32. 1, 1, 2, 3, 5, 8.
  33. And when I'm going to figure these out, I don't have to do a huge amount of work.
  34. Let's say I'm trying to figure out this 6th Fibonacci number.
  35. I can just look back in the table, and reuse my old work.
  36. I don't need to recompute the 5th Fibonacci number. I already have it here.
  37. Just additional those 2 chart cells together and get the answer.
  38. This is going to be our trick for making Fibonacci so much faster.
  39. It's called memoization.
  40. So we can implement our chart as a Python dictionary,
  41. just filling in the numbers as we compute them.
  42. So I can make an empty dictionary, assign mappings to my dictionary,
  43. and then check to see if something like 6 is recorded in my chart,
  44. and if it is, print out the result.
  45. This is going to be super necessary now and maybe it wasn't before.
  46. One of the keys to memoization is looking to see if you've already done the work
  47. and written it down.
  48. If you have, great! You can just reuse it.
  49. But if you haven't, you're going to have to go and compute it manually the first time.