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