, I wanted to show you one more idiom that helps us avoid repeated computations and

how it's useful. Turns out this idiom does not really use thunks, but that's okay

it's still worth knowing and it's called memoization which is not an English word.

But it is a technical word we use for this. And we really do leave the r out and

call it Memoization not memorization and it's been called that for a long time. So

here's the idea, if a function has no side effects and doesn't read anything that can

change. There's no point in computing it twice for the same argument. If you call

it twice with seven you're going to get the same answer. If you call it twice with

the same lists you're going to get the same answer. Doesn't matter how many times

you call it. So what we could do is keep what's called a cache of previous results.

Keep some data structure that remembers. Hey if you call this funciton with seven,

this is what you're going to get back. And this can be a great idea if maintaining

and using the cash is cheaper. Then recomputing the results. And if people

actually do the recomputations. They actualy call the same function with the

same argument again. Otherwise, the cache is a waste of space and a waste of time.

So, this idea is really pretty similiar to promises. That thing we saw with force and

delay, right? That when we do the first force, we'll store the result so any later

force just has the result there. But force of delay was for thunks that don't take

any arguments. Once you take arguments, you can't just have one thing that you've

stored for future reference. You need a table of them, depending on what the

arguments are. So that's where memoization is a little more sophisticated and I'm

going to show you an example where using memoization with a recursive function

actually leads to a program that is exponentially faster. And so it's a common

technique, something you can apply almost mechanically. That could actually lead to

programs that are much more efficient. other times, the y're just a little more

efficient, and it's still considered a convenient thing to do. So I'm going to

show the most of the rest of this with the code. I'm going to use this classic

example from memoizaton, this is what most people use. Here's an implmentation the

fibonacci function. This is a function for mathematics the same way we've been using

factorial, which says that the factorial n is n times factorial of n minus 1. With a

base case of factorial 0 as 1. Fibonacci is a little more sophisticated. It says

fibonacci is one for both 1 and 2. So just read the racket code here. If x is one or

x is 2, it's 1. Otherwise it's the sum of fibonacci of x minus 1. And Fibonacci of x

minus 2. So you see two recursive calls here. And turns out these two recursive

calls cause this to be a very inefficient implementation. This is exactly how it's

defined mathematically. You recall Fibonacci 1 with 30 you get a nice big

number like 830,000. But if you call with 40, this takes about a thousand times

longer to evaluate. And I don't have a thousand times longer to wait so I'm just

going to stop this. And say this is not a good implementation of the fibonacci

function. Okay so, what are we going to do about it? One thing you could do, which

I'm not going to focus on here, is throw away that algorithm, and implement this

other bottom up algorithm, that uses a local helper function that takes an

accumulator and starts at low numbers. And figures out fibonacci up to high numbers

by adding the 2 previous numbers as you go along. You're welcome to look at the code,

it's not that complicated. I just want to admit that this algorithm exists before

moving on and showing you a different way to do this efficiently that show this idea

of memoization. 'Kay, so, we're going to forget about that second version. Just

move on to the third version. I know it looks big and complicated. We're just

going to go through it line by line and see that it's just implementing this idea

of keeping around all the previous results. So, any time we compute Fibonacci

of anything we're going to put that in our table. And because we're going to do that

even when we make recursive calls it's going to in turn Fibonacci into an

effecient. Function. So let's see how that works. So the first

thing that you'll notice is that fibonacci ends up just being this helper function f.

So I'm going to define this function f here and then just return it. And the

reason why I'm doing that, is that I need f to use this memo table, this cash, this

thing that is initially null but is bound to this variable memo. It's essential, I

don't want memo to be at the top level, I don't want to define memo up here, 'cause

this is an implementation detail. I don't want to expose it to the outside world. ,

But I also cannot put it inside this function I'm going to define. 'Cause if

you put it inside, we're going to recreate a new table every time we call this

function. Because we do not execute function bodies until we call them. We

need it outside the table, so that it persists, so it's still around from one

call to the next. And it's initially null. Now, we're going to use mutation to update

it appropriately. Really. Okay, so when we want ca, find fibonacci

of x, so we just call x right here, okay? The first thing we're going to do is see,

is it already in the memo table. So, here, I'm using a little library function,

assoc, that takes in something and a list and tells you if that something is in the

list in the following way. Let me show you how this works. You can look it up on your

own in the manual, if you don't get this quickly. So let me define a little list

here. it has to be a list of pairs. Because pairs could have anything you want

in them, but how about just, three different pairs of integers here. Okay.

So that's a little list, xs just looks like this. What assoc does is it takes a

number like 3. And a list of pairs and it checks the car fields of the pairs for

something equal and with the first time it finds one, it returns that pai r. So a

assoc 3 xs returns 3, 4. Assoc 1 xs returns 1, 2 and if it's not in the list,

like 6 you do see a 6 up here but it only looks at the car fields, it returns false.

Meaning I did not find it in the list. So that's assoc. We're going to use assoc up

here, so I had to tell you how it works. So our memo table, which is initially

null, is going to be a list of pairs, and what it's going to be is argument dot

result. We're going to store in that list pairs of, if fibonacci, fibonacci of arg

is result. Alright? So here's what we do. If we find our answer in the table, so we

gotta pair here, and everything that is not false is true, so this works, and

return the cdr of that pair. We looked up the argument x, we found it, return the

result. So that's how we get our reels. In this else branch, we didn't find it. So

now all we have to do is compute it and then put it in the table so people can

find it in the future. So, how do we compute it? That's what this let variable

does, new-ans. We say, well, if x is 1 or 2, then it's 1. Otherwise it's adding

recursive call of x minus 1 and recursive call of x minus 2. Before we return,

change via set! memo to hold a bigger list. Take the old list memo, cons on to

it the pair of our new argument result pair. So that in the future, if anyone

needs fibonacci of x They'll find it in the table. After we've done that, return

this thing that we computed and that is the fibonacci of the number. So, this all

works and what might surprise you is that it's fast. I can ask fibonacci 3 of 1000

and I get this big number. No time at all. So why is this so much efficient than the

naive recursive version, that couldn't even do 40. I don't even think it could do

35. It looks like if it's not in the table, we're still doing these two

recursive calls, and it would blow up exponentially. But we are doing two

recursive calls, whichever one we do second. Will be very, very fast. See, the

problem with exponential blowup is that we make two recursive calls, and they m ake

two recursive calls, and they make two recursive calls, and it blow ups, blows up

2, 4, 8, 16 and 32. But what happens here is we make two recursive calls. The first

recursive call ends up filling up the table with lots of numbers. The second

recursive call ends up finding what it needs in the table. Especially if the

second one is with x minus 2. The second one is x minus 1. It will still have to do

one more recursive call, but then it will find what it needs in the table. And

that's only at the top level. After that, everything's already in the table. So

recursivly, at every step, instead of making two expensive recursive calls, we

make one recursive call. And then, for the next recursive call, everything is already

in the table. So this isn't just twice as fast, it's twice as fast at every level.

And in fact, it's taking something that would take time proportional to 2 to the

x. And turning it to something that takes time proportional to x. Or if you really

want to be picky, since I have to run down this list doing assoc, maybe x squared.

But x squared for a 1000 is nothing. that's no problem at all. Whereas, 2 to

the x, where x is a 1000, is more than I believe, the number of particles in the

universe. So that's our example. It's just a programming idiom. All we did was really

that something that had nothing with fibonacci itself. We created this table.

We always checked it first. If we found it, we did nothing else. Otherwise, we

compute our answer. And before we return, we add our result to the table for the

future. And that is Memoization.

Memoization

Programming Languages, Part B

与讲师见面