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

1. Title:
   04-07 Memoization
2. Description:

   dummy description

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