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