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