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.