[As described below, this is Part B of a 3-part course. Participants should complete Part A first -- Part B "dives right in" and refers often to material from Part A.] This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language “fits together” to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module of Part A. Part B assumes successful completion of Part A. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.
Memoization
Loading...
来自 University of Washington 的课程
Programming Languages, Part B
331 个评分
从本节课中
Section 5 and Homework 4 (First Module with Racket)
Let's get started programming with Racket and then learning idioms related to delaying evaluation. The welcome message has a few additional comments about picking up a new language and how to approach the homework assignment, so let's get started...
与讲师见面
Dan GrossmanProfessor
Computer Science & Engineering
, 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.
