WEBVTT 00:00:00.000 --> 00:00:03.000 You might have noticed that up here on the right, I made a very simple chart 00:00:03.000 --> 00:00:07.000 to try and explain how Fibonacci behaves to myself. 00:00:07.000 --> 00:00:11.000 We're going to use this same sort of chart to make Fibonacci much faster 00:00:11.000 --> 00:00:14.000 by voiding repeating a lot of work. 00:00:14.000 --> 00:00:23.000 Our official plan for this is going to be called Memoization. 00:00:23.000 --> 00:00:26.000 It's just like memorization, but missing an r. 00:00:26.000 --> 00:00:31.000 Here I've tried to draw 2 memos: a corporate memo and those yellow sticky notes 00:00:31.000 --> 00:00:34.000 you sometimes see, where you could write a little memo to yourself. 00:00:34.000 --> 00:00:39.000 A memo in English is just a document, a small document, that's written down-- 00:00:39.000 --> 00:00:40.000 memorandom. 00:00:40.000 --> 00:00:41.000 Why bother with this? 00:00:41.000 --> 00:00:46.000 Well, it's going to turn out that our current implementation of Fibonacci is super slow. 00:00:46.000 --> 00:00:47.000 Let me try to prove that to you. 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-- 00:00:51.000 --> 00:00:53.000 about .3 seconds. 00:00:53.000 --> 00:00:57.000 Let's up that a bit to the 24th Fibonacci number-- 00:00:57.000 --> 00:00:59.000 should take not that much longer, right? 00:00:59.000 --> 00:01:06.000 Oh! Significantly longer, from .3 seconds to 1.75 seconds. 00:01:06.000 --> 00:01:09.000 We went up a huge amount. 00:01:09.000 --> 00:01:13.000 Let's go up to the 25th Fibonacci number--oh! We almost doubled. 00:01:13.000 --> 00:01:16.000 We're now at about 2.8 seconds. 00:01:16.000 --> 00:01:19.000 In fact, we have reason to believe based on human studies 00:01:19.000 --> 00:01:23.000 that if a webpage takes longer than 6 seconds to get back to you, 00:01:23.000 --> 00:01:26.000 you go somewhere else and buy something different online. 00:01:26.000 --> 00:01:30.000 So we're already using up a huge fraction of that budjet just to compute 00:01:30.000 --> 00:01:31.000 the 25th Fibonacci number. 00:01:31.000 --> 00:01:35.000 And if you think about those trees I drew before, this is unsurprising. 00:01:35.000 --> 00:01:41.000 If we increase the number by 1, we almost double the work at each step. 00:01:41.000 --> 00:01:45.000 So this is untenable. We need something faster. 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. 00:01:50.000 --> 00:01:54.000 I'll just make a table mapping N to the value of Fibonacci of N. 00:01:54.000 --> 00:01:58.000 1, 1, 2, 3, 5, 8. 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. 00:02:02.000 --> 00:02:05.000 Let's say I'm trying to figure out this 6th Fibonacci number. 00:02:05.000 --> 00:02:09.000 I can just look back in the table, and reuse my old work. 00:02:09.000 --> 00:02:16.000 I don't need to recompute the 5th Fibonacci number. I already have it here. 00:02:16.000 --> 00:02:19.000 Just additional those 2 chart cells together and get the answer. 00:02:19.000 --> 00:02:23.000 This is going to be our trick for making Fibonacci so much faster. 00:02:23.000 --> 00:02:24.000 It's called memoization. 00:02:24.000 --> 00:02:27.000 So we can implement our chart as a Python dictionary, 00:02:27.000 --> 00:02:30.000 just filling in the numbers as we compute them. 00:02:30.000 --> 00:02:35.000 So I can make an empty dictionary, assign mappings to my dictionary, 00:02:35.000 --> 00:02:38.000 and then check to see if something like 6 is recorded in my chart, 00:02:38.000 --> 00:02:40.000 and if it is, print out the result. 00:02:40.000 --> 00:02:44.000 This is going to be super necessary now and maybe it wasn't before. 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 00:02:48.000 --> 00:02:49.000 and written it down. 00:02:49.000 --> 00:02:52.000 If you have, great! You can just reuse it. 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.