0:22

In the last lecture, we went through and tried to count

Â the number of operations in the various pieces of your program

Â and derive some expression that gave us, some intuition about the

Â running time of your program based on the size of its inputs.

Â 0:35

In this lecture, we're going to take a different approach.

Â We're going to think about instrumenting your code.

Â To kind of, count the number of operations.

Â And then we're going to plot the size of the input, versus the running time.

Â 0:47

Plotting this data will give us a, give us a

Â nice way to kind of analyze the behavior of that data.

Â Turns out that humans are visual creatures, so looking

Â at a plot of a data is actually much

Â more effective than looking at, say, some raw dump

Â of the data or some kind of raw table.

Â I'll, I'll give you an example.

Â 1:04

Here's a, actually a well known image.

Â It's Scott's level of agitation as a function of the

Â number of global variables that you use in your code.

Â No, that's not really true.

Â It's actually a plot of kind of global temperature over the last 125 years.

Â This particular picture has inspired billions of words of discussion.

Â It's a good example of kind of the power of using visualization to understand data.

Â 1:30

So what we're going to do, is we're

Â going to start off, we'll take some mystery code.

Â We'll instrument it, we'll generate some data, then we'll figure

Â out how to plot it using a package in code sculptor.

Â And then we'll do some quick analysis of that data

Â to try to understand the running time of this mystery function.

Â 1:52

So if you look on the screen here, I have three functions that I've defined.

Â Mystery 1, mystery 2, mystery 3.

Â I've used code folding to hide the body of these functions.

Â When you load them in, you can either look at the

Â body or you can fold it up and hide it yourself.

Â 2:07

But the problem that we're going to try to

Â attack here is to understand the running time, kind

Â of the length of the execution trace for each

Â of these mystery functions as a function of input_val.

Â So as I change input_val, each of these functions takes longer to execute.

Â We kind of like to know, kind of what's

Â the relationship between input value and the execution time.

Â So to do that, what I've done is I've built a

Â global counter, I'm sorry Scott, and I've essentially inserted in the

Â execution of each mystery function a statement that increments the value

Â of this counter each time we do whatever we want to analyze.

Â In this case, we have a collection of loops.

Â So every time we execute the body of

Â the innermost loop, we increment the counter by one.

Â 2:48

So, then I built this plotting function down here that I can

Â pass in a plot size, kind of the range for the input values.

Â The function we're going to plot, mystery 1, mystery 2 and mystery

Â 3, and then the plot type, we'll talk about in a second.

Â So then, here's what happens.

Â It's very simple, we're just start out with the plot that's an

Â empty list, and we choose var, various values for the imput size.

Â We run the plotting function, and then we grab the value again, put val, grab

Â the imput value in the counter, and append it to, at the end of the plot.

Â So, the result of this is a list

Â of points, in a kind of two dimensional space.

Â Their input value versus the counter size.

Â 3:22

So, what we like to do now is actually

Â figure out how to make sense of that data set.

Â So, we're going to talk about plotting [SOUND].

Â Okay, let's talk about how to plot data.

Â 3:35

So the basic idea is, we created this list of points.

Â And we'd now like to make a picture of it.

Â So, in Python, the standard method of doing this is, choose a plotting package.

Â 3:45

Now, we're at Python.org here.

Â There's literally, if you look as this, there's

Â dozens of various packages available for doing plotting.

Â 3:54

This is a little bit like what we faced when we used Simple

Â GUI versus TK Enter or Pie Game or WX Python would be my guess.

Â There's lots of different packages for doing GUIs.

Â There's lots of different packages for doing plotting.

Â If your working in idle and you want to stay

Â basically, slow down the desktop, pick one of these packages.

Â Read over it.

Â Figure out how to use it.

Â It shouldn't be too hard.

Â And you can plot your data.

Â 4:17

We've provided a custom plotting package inside Code Sculpture.

Â It's extremely simple.

Â It's called simple plot.

Â It basically allows you to make line plots.

Â It's there for your convenience.

Â I'm going to use it in the example here because it's

Â easy to do and works very nicely inside code sculpture.

Â You're not required to use this though.

Â But the critical thing to understand here is the philosophy of Python.

Â 4:38

When you want to pick up and learn how to do things

Â you're gona have to understand how packages written by other people work.

Â That's a part of the survival skills inside Python.

Â So, when your here this things says well, why don't you treat me

Â the right way to plot or the right way to build a GUI.

Â In Python, there are many different ways to do this and so the ability to move back

Â and forth between packages is a key skill

Â that you're going to have to hone in this class.

Â All right, so let's talk a little bit about how SimplePlot works.

Â You can find it in the docs here, under

Â the documentation, you click on Graphics Modules, scroll down.

Â There's really only two operations you can do in SimplePlot.

Â You can make a line plot or you can make a bar plot.

Â The syntax is here.

Â At this point, you should be able to basically

Â read the docs and figure out how to do it.

Â I'll go back and show you an example inside my code her in just a second.

Â [SOUND] Okay, let's do some plotting.

Â So we'll return back to our example code.

Â From here you see my three mystery functions.

Â Here's my plotting function that actually builds the

Â plot, and down here what I've down is I've

Â called that function build plot three times with

Â a plot size of 40 for each of those.

Â I pass in the names of the three mystery

Â functions, and I'm going to do a standard plot for now.

Â And so here's a critical layout called simple plot, the plot lines.

Â And one of the things that we really gotta pay attention to

Â here is we can give it multiple sets of data to plot.

Â So we give it a list with the three plots here.

Â So this is a list.

Â Each of these entries is a list of points.

Â So, when I click Run.

Â 6:17

This is the plot of the second function.

Â This is the plot of the third function.

Â So just by looking at this, we can

Â kind of deduce some simple properties of these functions.

Â On the first functions looks like it's linear.

Â 6:28

So what that really means is, that if we

Â look at the input value, the number of steps

Â we're taking in this, the, the value, the count,

Â is going to be a linear function that input that you.

Â So particular, if we double the size of the input value.

Â The number of, the value of the counter of

Â the number of steps in there would actually double.

Â The second and third functions is a little more unclear.

Â It looks like they might be polynomial functions.

Â Maybe it's quadratic, and this one's cubic.

Â 6:55

It's important to know whether a function is polynomial versus say exponential.

Â For example if a, if a function is quadratic and we double

Â it, the, the running time just goes up by a factor of four.

Â If it's cubic the running time goes up by a factor of eight.

Â But if the function is exponential then we double the size

Â of the input, we square the running time and just, goes crazy.

Â So in fact exponential functions we want everybody to

Â run them for a large input in most cases.

Â So what we're going to do next is let's talk

Â a little math and I'll show you kind of a

Â trick to answer, answer the question about whether these

Â functions are actually polynomial or not, we're going to use logarithms.

Â [SOUND] Okay.

Â During the course of this class you work with two functions occasionally.

Â Lets go over those functions very quickly here.

Â You may do word take logarithms and you may do exponential.

Â So an exponential you've probably see in high school math.

Â You take some number and you raise it to a particular power.

Â 7:52

We're going to actually use the

Â natural exponential function here fairly frequently.

Â Sometime [UNKNOWN] to the xp of n.

Â And all it really is is Euler's constant, which is 2.718 arrays to the nth power.

Â Euler's constant is a magic number.

Â You can look at the Wikipedia page, if you want to understand where it comes from.

Â But, for, now just think of it as a constant between two and three.

Â 8:13

The second function we're going to work with is logarithm.

Â We're going to take use the natural logarithm again, fairly frequently.

Â So the natural log of a number n, we just simply take it to base c.

Â It's the, it's the power you have to raise e to get n.

Â 8:28

These functions are actually inverses of each other.

Â Which means if we take the exponential and then

Â we take the log, we get back the original input.

Â Or we take the log and then take

Â the exponential, we get back the original input.

Â Notice that in some cases you want to work with a different base.

Â You want to do base 2 or base 10.

Â The typical notation you will see here is

Â log with the subscript that corresponds to the base.

Â Probably the most important thing

Â to understand about exponential and logarithms

Â are they kind of obey the following two rules down here.

Â 9:14

With logarithms, it's kind of the complementary thing.

Â If you have the logarithm of the product of two numbers,

Â it's simply the sum of the logs of each of the numbers.

Â Okay, this is a very useful piece of information here.

Â So next, I'm going to show you how to go

Â through and actually use this to do log, log plotting.

Â [SOUND] So, we've taken our mystery functions, we've built a plot of

Â them, and now we're trying to understand the behavior of the, kind of the,

Â running time, the value of this counter as a function of this input value.

Â So kind of a metric for whether you've got a reasonably behaving function

Â is to ask, is the running time a polynomial of the input value.

Â So we kind of like to ask, okay, x is the input

Â value, it's the running time y, is some polynomial function of it.

Â 10:06

So it turns out we can use logarithms

Â to help kind of understand and answer that question.

Â I mean here is the trick.

Â If y is equal to a times x to the n, we take the log of

Â both sides, we get log of y is equal to log of a x to the n.

Â Remember the product rule for logarithms says we can break this apart.

Â All right, this is log of a plus n times log of x.

Â 10:29

So if our data points actually satisfy this relation, y equals a

Â times x, y equals a times x to the n, then the

Â data points should have the property that the log of the y

Â value should be a linear function, of a log of the x value.

Â 10:47

So in fact, this is a strategy we can use when we're actually

Â plotting our data to figure out if our data lies on a polynomial curve.

Â We'll take the log of the x, and we'll plot it versus the log of the y.

Â And if that's a straight line, then guess what?

Â The data lies on a polynomial function.

Â And in fact, it's even better.

Â If we look at the slope of that line, the slope of that line is exactly n.

Â It's the degree of the polynomial.

Â 11:11

So in fact, this is a trick behind something that

Â you'll see in lots of plotting packages called log, log plotting.

Â It's hidden a little bit because what they'll do is they'll take the

Â labels on the axis, instead of

Â spacing them evenly, they'll space them geometrically.

Â You might see this where you'll see the label be 1, 10,

Â 100, 1000, 10 thousand, 100 thousand, a million and they're all equally spaced.

Â What they're doing is they're basically doing this log trick here.

Â So what they're doing is they're plotting the data

Â point by taking the log of each of the values.

Â That has the advantage of if the data grows really

Â quickly, you can still make some sense out of this

Â because instead of getting a wildly growing curve, you get

Â a curve that's perhaps, perhaps maybe growing as a straight line.

Â So lets go back now and look at the three functions and do a log, log plot of them.

Â [SOUND] Okay lets finish off our example.

Â So, here we are back in our Python code.

Â 12:08

The cool thing is we can actually change that.

Â And what you'll see up here is instead of plotting the input value versus the

Â counter, we'll plot the log of the input value versus the log of the counter.

Â It'll be the log, log plot.

Â So I can change this to LOGLOG and I'm going to hit Run.

Â [SOUND] And what comes out here is a plot and what you can see

Â here is that the LOGLOG plot of this line is again a line.

Â Probably something more interesting here is our second curve.

Â Our second curve, the one that we thought

Â might be quadratic, well, we do the log, log

Â plot of it, what we see is that,

Â yeah it's pretty much growing like the straight line.

Â And in fact if you look at it, it looks like the slope is two.

Â So in fact, I think this is probably growing quadratically.

Â This last one though, look, it's not going as a straight line.

Â I thought it might be cubic, but it's not.

Â 13:06

so, probably this, this last one is, may not be a cubic.

Â It may not be, may not even be polynomial.

Â So let's go back real quick and look at our

Â functions and just kind of see what the mystery functions look like.

Â [SOUND] So the first one was really simple, it was

Â just going through and doing kind of just five iterations

Â of inner loop for every value and every value and

Â input value range, so that's, that's 5x, it's linear easily.

Â This one here, if you look at it, it was doing some plotting but at the

Â end of the day it's kind of two nested loops and this is, this is quadratic.

Â 13:41

This last one actually is, is actually not quadratic.

Â In fact, you kind of see this magic 1.1 to some power.

Â It's actually doing a very slowly growing exponential function.

Â So if we had, had turned out that our mystery function was actually growing

Â in this rate, you probably wouldn't be able to run it for really large values.

Â So we could kind of see that when we did

Â the log, log plot, that we didn't get a straight line.

Â 14:05

So, hopefully this lecture's helped you to kind of gather more knowledge

Â about exponentials and logarithms and given you some insight into how we could

Â go about analyzing the running time of our code even if we

Â can't do some kind of close analysis based on looking at the code.

Â [SOUND]

Â