Tip:
Highlight text to annotate it
X
Now to show off how insanely great memo is,
we'll want to have before and after pictures, showing the amazing weight loss of a model
that was fat before and was thin after applying memo.
Oh! Wait a minute. It's not weight loss. It's time loss that we're going to try to measure.
We want to show that before, we have a function f, and that's going to run very slowly,
making us sad.
And after, we have a function memo of f, and that's going to run very quickly,
making us happy.
Now we could do that with a timer and say it took 20 seconds to do this
and .001 seconds after,
but instead of doing it with timing, I think it's a little bit more dramatic just to show the number
of function calls, and I could go into my function and modify it to count the number
of function calls,
but you could probably guess a better way to do that.
I'm going to define a decorator to count the calls to a function because I'm probably
going to want to count the calls to more than 1 function as I'm trying to improve the speed
of my programs.
So it's nice to have that decorator around.
So here's the decorator countcalls,
you pass it a function, and this is the function that it returns.
It's going to be a function that just increments entry for this function in a dictionary callcounts.
Increment that by 1 and then go ahead and apply the function to the arguments
and return that result.
We have to initialize the number of calls to each funciton to be 0,
and that's all there is to it.
So here I've defined the Fibonacci function.
Through cursive function it calls itself twice for each call, except for the base case.
I can count the calls both with and without the memoized version.
So I'm going to do before and after pictures--before and after memoizing.
So here's before.
I have the values of n and a value computed for Fibonacci number of n,
the number of calls created by countcalls, and then I have the ratio
of the number of calls to the previous number.
We see the number of calls goes up by the time we get up to n = 20.
We got 10,000 calls.
We can scroll down, and by the time we're up to n = 30,
we have 2.6 million calls.
And here's the after.
Now we've applied the memo decorator.
Now the number of calls is much more modest.
Now at 20, we're only at 39 calls, and at 30, we're at 59 calls rather than 2.6 million.
So that's pretty amazing weight loss to go from 2.6 million down to 59,
just by writing 1 little decorator and applying it to the function.
Now just as an aside here, and for you math fans in the audience,
I'm back to the before part. This is without the memoization.
This number here in this column is the ratio of the number of calls for n = 30
to the number of calls for n = 29.
You can see that it's converging to this number 1.6180.
Math fans out there, I want you to tell me if you recognize that number.
Do you think it's converging to 1 + square root of 5 / 2,
25.888 / 1600,
or the square root of e?