CSC300: Thinking about loops

Contents [0/21]

Video [1/21]
What does this function do? [2/21]
How do you know? [3/21]
How do you know? [4/21]
How do you know? [5/21]
You don't need the code! [6/21]
Manual Testing [7/21]
Automatic Testing [8/21]
Using an array of length 3 [9/21]
Using a loop [10/21]
Generalizing [11/21]
Loop invariant [12/21]
A bad solution [13/21]
Exceptions [14/21]
Designing loops from scratch [15/21]
Solution with while loop [16/21]
General rules for desiging loops [17/21]
Another way to compute max [18/21]
Another way to compute max [19/21]
Using a timer [20/21]
Conclusions [21/21]

(Click here for one slide per page)


Video [1/21]

In two parts

Open Playlist

hi there i want to start talking to you about programming so if i give you a program like the one on the screen and i ask you what does this do um can you tell me so pause the video for a sec think about it and start it back when you're ready with your answer so what does this do well you can see it takes three variables x y and z initially we sign m to be x then if m is less than y we set m to be y and if m is less than z then we set m to be z and then finally we return m all right so what's going on there well um if we think of you know specific numbers maybe it's helpful let's take one two three so if m is initially one um then here one is less than two so we'll set him to be two oh and then if two is less than three we'll set this to be three so we'll return three ah so it seems to be picking the largest number indeed this seems to be the max of three numbers um and you can see that this actually works generally even if they're in a different order so if i have one three two will still be fine because we'll start off with 1 then here we'll assign 3 because 3 is bigger than 1 but 2 is not bigger than 3 so we won't execute this statement so this is actually computing the max sort of abstractly what are we thinking about here well the reasoning what's actually going on in your head when you think about this program is you start off thinking well what is the value of m m initially is the max just of x i mean so it's x but it's it's also the max of x the max of x is just x and what's happening with each line we execute is we're expanding the scope of the max by one additional variable so after we've executed line four we can see that we've now determined that m is not just the max of x but it's the max of x and y um and now by taking the max of x and y and comparing that to z we can determine that on line seven we have the max of x y and z so all of these things um so that's great and and what's really interesting about this way of thinking about programs is that when you start looking at it this way really you don't need the code so what we're doing here is we're initially setting m to be the max of x then we set m to be the max of x y so we're going from max of x to max of x y we're going from max of x y to max of x y z and so you can see that the the lines of code that i've got in there are simply getting me from one step to the other so we're establishing the initial premise that m is the max of x and then knowing that we can add in y and then correspondingly add in z and looking at the code in this sort of logical way um is actually what your brain is doing when you read code so if you're actually reading code and genuinely understanding it then your brain is going through this kind of process um and so being aware of it can be really helpful so you know when we write code we often want to actually test it so you know i i think i just reason through this code i'd like to um you know i'm convinced that it's correct um but maybe there's a small error and so it's useful to actually have some tests so so since code is automated what we can do is we can sort of take this code and we can type it in and we can sort of see what it does so i'll just run this and see what the output is and um you can see that it does work so what i've got here is in each case the max is 31 and i'm running three different tests for three different positions because i want to make sure um you know that i'm i'm not got some funny little bug and you can see this kind of test will work so if i do have a typo you know sometimes the code is correct but you know morally correct um but you've got a typo when you entered it like copy and paste error this kind of thing is quite common but what we're doing here is what we call manual testing so in order to check this i must visually inspect the output this is not gonna scale so you can imagine uh if i have a very large program checking all these little tests is to be a big problem um and it works this kind of testing makes you conservative as a programmer so you know the problem is you you run your code you get it to pass the test so i'm like okay this is not right i gotta get that to be a z now everything's great okay pass the test um and then usually what people do is they don't remember this stuff they just wipe it out to their their test and they'll just start um you know proceeding but now if somebody says hey you know that max function you could write it a different way um is it is that fine like let's say i want to swap these two i want to put the the comparison to z first is that okay well probably um but in the absence of the test you might be insecure to make this change so what we say is that the code can become brittle if you have these kind of manual tests so a better approach is to what we do what we call automatic testing so there's a little bit of work here you can see that there's some stuff i have to write out but but it's in general worth it so this is not something you probably would have done in your first programming class because in your first programming class it's sort of one and done you write the code you get it to work you're done that's not what we're doing here so in general code doesn't work like that you're usually programming for another programmer you're writing a program that's going to be around for hopefully many years and there'll be small changes in maintenance done to the code and it's important that that people be able to develop some confidence that their changes haven't broken anything that you had originally um created so what we'll do is uh something like this i'm going to write a test function here called test max what test max does is it takes the values x y and z and an expected value what we're going to do is we're going to run the max function on these parameters x y z and see what actually comes out and we'll check to see if the expected value is equal to the actual value and if they're the same well that's great we don't need to do anything everything was hunky-dory otherwise we need to inform them that the test failed right so in general passing tests are usually silent because we expect tests to pass we really only want the squeaky wheel when a test fails so if you print out stuff for passing tests you end up with too much noise and it's it's impossible to tell what's going on um so let's just see what this does here so when i run this test um it can see oh it failed why did it fail uh well oh i did that intentionally so this is a failing test so what it says is here i was expecting 31 but i actually got 21. and the arguments were 11 31 21 so it failed in this case and and just by inspection i can see what the problem is there's just a typo there so if i fix that then it'll finish the test this little thing at the end is helpful um if you leave this out it's sometimes it's disconcerting because you run the program and you just get silence silence is is it working is it not working you could have an infinite loop here so if you just put in some sort of well while loop or infinite loop the program will just hang forever so you can do something like this while true just do nothing um and it's kind of tricky to see the difference between an infinite loop and a passing test so here you see this little red button here that's saying that the program is still running so i can terminate it but so there you can see the program has terminated now so you can see that the program does terminate here because it's no longer giving me a red button we're going to be doing this style of testing this class because it's relatively light um they're i mean it doesn't need many tools and stuff there's a huge amount of frameworks for doing this kind of testing so you can pick your language and even for just java there's a huge amount of frameworks to do this the one that i've used in the past is called junit is we will use these in later courses at depaul in particular in software engineering we'll talk about using testing frameworks um but for us in this course it's just extra weight we're not going to bother with it so we're just going to write these kind of manual automatic tests so um i'm going to write for your homeworks you'll find these test functions you'll find a main program with tests like this i've written this function here to take three variables x y and z i could equally have written it to take an array where i'm just going to look at the three elements of an array so this is how you do this and to make things just clear when i use arrays i'm going to use doubles rather than ins as the kind of the values of the array and that's because arrays are indexed by integers so it's nice to have that contrast between the index which is an int and the value in the array which is a double so here's an array of doubles and you know the code here is is absolutely unchanged so here i've got the max of three things x y and z of course this has a bug that should be y but what i'm doing here is the same i'm just calling them a0 a1 and a2 of course the way we invoke the function now also changes instead of passing three separate parameters i'm passing a double array and the way we can instantiate a literal double array in java looks like this so here um i'm passing in the array with elements 11 21 and 31 i'm expecting 31 to be the result so let's see if this still works yes okay so um and the same reasoning applies i'm doing exactly the same thing going through these three elements note that we have two statements here which are identical except for the index so at this point we have a of one on one line at af2 on another line and you know we can get rid of that commonality you could imagine we did this for a four place array we'd have uh four lines or five place array we'd have five lines so we can get rid of that redundancy by using a loop so what we're doing here is we're initially going to execute this line for i is equal to one we'll check to see a of one and then we'll do it for a of two okay so we're doing it for one and then for two and so we're just doing it twice so this will now execute here where i is 1 and then where i is 2. note that we will not do it for the case where i is 3 because 3 is not properly less than 3 and therefore this loop will not execute for the value of 3. again the syntax here in java is to pick in a for loop we say that i is initially 1. we want to increment i by one each time and we're going to stop when this predicate becomes false so when i is greater than or equal to three we'll stop okay and this runs beautifully um what we've got i mean at this point though you can see how arbitrary the choice of three is so three the number three here um feels very out of place like why is three here um why are we only dealing with the rays of size three that does seem fairly arbitrary so what we can do instead is work with an array of any length and we can do that by using the length field of the array classes in java so each array has a length associated with it and so we can just use that length as our bound so note that if we have an array with three elements the length will be three and the indices for those elements will be zero one and two so the way we go through them is something like this we have a of zero i can then start here at af1 this will go up to af2 and then again once i is equal to the length the loop will not execute so when this becomes false um so the index is not properly less than the length we'll exit the loop this is sort of the standard way to go from the beginning to the end of an array um and this function works just fine and you can see now i can actually use different lengths arrays and they should work out fine so here i have tests where i'm going to check a 2-0 mount array uh check a single of them an array no problems this should all just work fine and so we can run it and should be fine yeah it's all good the the thing that we've written here is still correct and i i think it's important now to look at it again that we've generalized to an arbitrary length array just to see what we've done right so what what's happening is that each step we're increasing the number of elements we've looked at by one so um and we're using a variable to keep track of how far we've gone so the variable is called i and what we're doing here is keeping track of the elements from a of zero up to a of i minus 1. so at each time through this loop we've looked at all of the elements from a of 0 up to a of i minus 1. so let's see if that's i'm going to claim that's true let's just check it to make sure that i'm saying the truth so initially m is a of zero so um when i is one have i really looked at max of a of zero up to a of i minus one well yeah this is um in this case when i is one one minus one is just zero so i only have to have looked at one element which i have i before the loop even starts i have looked at a of zero so it holds at the beginning um and then as i make a step right let's suppose i've looked at i elements um is it true that when i increment i um i only do that after i have looked at the ith element and in fact this is what's happening so assuming that m is the max of say the first three elements now if i look at the fourth element i can then say after the loop has gone around that i've now looked at all four elements so each time through the loop i'm adding one more element and then the key here is that when i get to the end of course i is going to be equal to a dot length and therefore this invariant will tell me that m is the max of the elements from a 0 up to the length minus 1. and of course that's all of them okay so that is all of the elements in the array and therefore i can safely say that this is really the max so what we're using here is what's called a loop invariant this is something that is true every time before we execute the body of the loop so the body of the loop here is just line eight and before we execute line eight this statement is always true um and it's also true when we exit the loop which is um really very nice and this is what's sort of the reasoning this is actually um if you look at how you read code you'll find that if you really understand a loop you're doing this kind of reasoning in your head there's no way to understand a loop without doing this kind of reasoning right so we we have to be able to think about what's happening each time around and generalize it into some abstract form so that we can sort of um understand what what the loop is doing as it progresses this code is excellent and it's handled arrays of arbitrary length but there's one assumption in the code that makes it a bit brittle which is that we're assuming that the array has at least one element so in fact i can try this on an array that has no elements and what is this code going to do so first of all you might wonder is this valid java and you can see that eclipse is fine with it so we can execute and oh that's not nice so what we've gotten here is what's called an array index out of bounds exception one thing that's wonderful about java is that when you get an exception it will tell you exactly where that occurred so you can see what line it happened on um it happened here and so you could just click that and see and it'll tell you actually the array index out of bounds exception will tell you that index 0 out of bounds for length 0. so indeed you can see which test failed because we were actually on uh in the main program on line 24 so it was actually this test that failed and that makes sense so the array has length zero i'm trying to look at the zeroth element that's not okay okay so and it's obviously nothing to do with the value i chose here this is just because i'm looking in the array in this way in this case we need to check if the length is zero then we need to do something so what do we do um most beginning programmers will think well i'll just do something like this i'll return zero okay whatever and this is sort of a um a solution that does get it to pass in this case i have a value um but is zero a good choice here i mean it turns out that zero is just yet another magic number um it's completely arbitrary and these kind of magic numbers are just bad you don't want to have them in your code they're going to make your code brittle it's going to break in certain cases so in this case what we've done is identify the empty array with the array that just contains zero or in general any array that contains zero as its max i mean we could have a bunch of negative numbers and then a zero and then the max is gonna be zero so um having that be the value for the empty array seems kind of wrong in this particular case there is a value we could use it's um called double dot positive infinity or sorry negative infinity is the one i want so double dot negative infinity this makes some mathematical sense if you think of the mathematical definition of max this is an identity value for the max but there's many cases where this kind of mathematical identity doesn't exist and so um you know there's often just not a good choice for for what you should do in this case um so i mean you could just say well screw it we're going to throw an exception and java's already throwing an exception so we should be fine with that but this exception is not very informative it's it's uh it's giving us the wrong information in some sense so what we'll do is to make it clear that we intend this exception to happen we'll use a different exception so in this case i i would put in my documentation that the double needs to be non-empty so we could add a comment here this double array cannot be empty and we can also document this by throwing a particular kind of exception so the common one for this kind of case is an illegal argument exception so it's saying that the argument a that you gave me is not a good argument so um so we can run it the code there so this is an illegal argument exception um and exceptions are very useful this is what they're essentially for is these kind of exceptional cases and that's why they're called exceptions um the the mechanics of them is not particularly complex and i don't want you to get too uh obsessed with you know all the details of exceptions but when you want to the idea here is to throw an exception and then it can be caught by a calling function so here i am throwing an exception from max meaning max doesn't have a good return value at this point and so it throws that out to the outside world um if the outside world is expecting this exception it can catch it so this is the way you do this in java is with a try catch statement so i'll try to call max not sure it's going to work and here if it fails then i'll catch that exception in this case i actually want the exception so here i'm trying to test the code to make sure it behaves the way i expect so i'm actually expecting the code to throw an illegal argument exception so that's what i want so i'll if i catch the illegal argument exception i just do nothing um instead if the code does not throw an illegal argument exception then i'm going to be uh upset that's not what i want so in particular let's suppose we return 0 here then we'll fail here because i was expecting the illegal argument exception not some other thing so this is a failed test 
00:00 Logical thinking
03:45 Testing
10:11 Using an array as the parameter
11:49 Looping over the array
13:22 Three is a magic number: use array length
14:58 Understanding the correctness of loops
17:24 Invariants
18:22 Exceptions and debugging
19:56 Zero is a magic number: throw an exception
22:41 Testing exceptions

Open Playlist

here i have a test written and i can now try and develop the max function we're going to try and develop it from scratch so the way i suggest you do this is to start working with an example um so let's work with this example where we have 21 41 31 51 11. and i suggest that you start sort of in the middle of the process of determining whatever you want to do in this loop so let's suppose we've already looked at the first three characters and we're just looking at the fourth one which is 51 here now if my loop has already gone through the first three i need to have determined stuff about the first three in order to know what to do now that i'm seeing the fourth one and so the process of designing an algorithm here or a loop is to think about what you need to know in order to make progress so one thing i could certainly determine is the maximum number of the previous three so if i if i know the max of the previous three then by just looking at the next number i can compare this number to the previous max and i'm good to go that's sort of the way the algorithm we had worked so i mean one thing is i do need to know where i am so there needs to be some sort of marker to say oh currently i'm on the fourth element which is index three um so i i need something the typical name for this is i so that's for index um so that's my index into the array so in this case i would be 3 telling me where i am and so what i'm actually doing here then is i'm comparing the element at index i so that's written a of i and i'm going to compare it to m so i'm comparing these two things oh wait what's what's m so m ah so i need to know the max of all the things i've looked at so far so at this point the max would be what 41 so i need to know what was the max so far so there needs to be something to hold that so let's call that m okay and so what i'm doing is i'm comparing the max so far so if the max so far is less than a of i then i want to update the max so that it is a of i no so like like yay um yeah getting used to the syntax of java may take you a little while it's uh you'll get used to it you just need to know where the semicolons and the curly braces go um okay so this is uh the line that actually makes this progress then so um that's great this will actually look at 51 then and compare it to 41 the previous max and update the max to be 51. at this point i have actually looked at a of i and therefore it's important to make progress i'm going to update i as well so we'll increment i by one there's lots of ways of writing this um in in java you can write it as i plus equals one or just i plus plus these all do the same thing all right so um there i have made the body of my loop all right so where do i stop well it's important i don't look at a of a dot length because that is beyond the end of the array and i'll get a an exception if i try to do that so it's important that i stop when i is equal to a dot length so i'll continue as long as i is properly less than a dot length okay so now we just need to figure out what these uh values are and well for for the value of m i'm i'm going to assume that the array has at least one element so we'll take that to be a of zero and note that i've already looked at a of zero so i don't need to look at it again so i'll start i at one in fact so it might be better you know this is just fussing around but um so it might be better to write it this way so a m is a of zero and now i know that i've already seen zero so i don't need to start there i'll start with one um and continue you you i if you were to write your code like this um where you're actually looking at zero twice it would work but it would confuse anyone who tried to read your code so unnecessary work is always bad not so much because it takes more time or anything like that it just makes the code harder to understand so if you're doing something like this someone who's reading your work would be like really do you need to do that you know why why um and so they're going to have a question about it whereas if you write it where you're doing only the work necessary um then any reader will immediately understand what you're doing and they won't be questioning you know what what is going on in the code okay so there you go so that's this code in a while loop so once you've getting this all settled down and it looks like it's going to work you need to worry about corner cases so corner cases are things like empty array so what if somebody gives me an empty array well poo i'm not going to be able to work with that so what i'm going to do in that case is um uh i'm going to throw an exception a new illegal argument exception there we are okay so that's fine um one thing you'll notice that curly braces are optional in java for single statements so i don't actually need a curly brace here um it's not a bad idea to put it in though so they're they're not required if you only have one statement inside your if um if you're ever confused about what exactly you think your code is doing it's always handy to try and format it and see what eclipse thinks it's doing you see eclipse will actually spread out the curly braces and everything in a certain style you can make sure it sort of corresponds with what you think is going on okay um so this is nice there i have a function and we sort of derived it and this is indeed the code if you want to see the while loop version of this using a while loop or for loop doesn't matter it's exactly the same so while loops and for loops and java are interchangeable all right so let's just talk generally about what we just did so whenever you want to design a loop what you want to do is pick an example and start in the middle i think this is the most important thing don't start the beginning don't start at the end start in the middle assume you've gotten some way through the array and now you need to make one step of progress so if in order to figure out how to make a step of progress you're going to have to look and figure out what you need to know so you almost always need to know where you are and you need to know something about the things you've looked at so in this case we're keeping track of the maximum of the things i've looked at and so at each step i'm just looking at a new value and seeing if it's bigger than that previously computed maximum and so this will tell you what variables you need so in this case in addition to the index i i need a double m to keep track of the previous max so once you have that you can sort of write the body of the loop out and then you can sort of figure out how it's going to end it's like where do i stop and then you figure out how to start everything up get the initial values and then you deal with these corner cases okay so whatever they are one common mistake of beginning programmers is to think that variables always need to start at zero it's just not true so don't do it um starting at one often makes a lot of sense so uh starting at two might make sense depending on your application okay so it's not always going to be zero your initial value all right so that's a general way for designing loops there's actually many different ways we could compute the max so i've given you one it's not the only possible solution there's an other things we could do so um let's let's think about one of them i'll just leave this in here because that takes care of this case but um let's suppose that instead of doing things this way um actually let me just get rid of all this stuff there we go so um oh by the way i need to return the in the previous code right i need to return the max that i computed not one um that my test would catch that for me um okay so let's think about a different approach so what i'm going to say is all right let's suppose that instead of knowing the max so far i don't actually know that but i do know that none of the numbers i've looked at so far were the max so when i look at this number then i just need to see is it the max and if it is i can return it yay um if it's not then i just skip it and go on to the next one all right so in this case you end up with a very very different bit of code so in this case what i need to do well just to refresh your memory so before what we were saying is if m is less than a of i then i was going to set m to be uh a of i right that's how we were making progress last time um what i'm going to do here instead is to say oh okay well if none of the previous numbers were the max then um how do i find out whether or not this number is the max well it's pretty straightforward so i want let's suppose i'm at the ith number all right um i'm at number i and what i want to do then is check a of i and i just want to see if any number in the array is bigger than a of i if any number in the array is bigger than a of i then i then i didn't find the max okay so how do we do something like that well we have to go through the whole array so let's use another variable we'll call it j to go through the array and to go through the array arrays it's always kind of the same process right from here starting from zero up to a of i minus one uh the length minus one and i'm going to increment j okay so for all of the elements of the array what do i do well i'm going to see if a of i is if if a of i is smaller than any element of the array then uh if it's smaller than a of j um then what am i going to do well i know it's not the max well uh what am i going to do with that knowledge i think i need a variable so let's let's create a boolean something like is max um initially we'll say it's true okay so we'll assume that i am the max and now if i see something bigger than a of i then i'll say well is max is false okay there we go that should work something like that and then after i've gone through there i can say if ismax is true then i found the max so i can just return it at that point i don't need to keep going i can return a of i that would be the the new max okay oh okay this is interesting so we need to do this for every i um and so what we're gonna do is do this for what i um from zero up to i minus right up to the length there we go so we'll do that for every i um the indentation has gone all whack-a-doodle so um let's get rid of this decoration we don't need that and now let's indent oops okay um we're starting to look good and i think yeah we're almost making sense okay so let's see so for any i so eyes going from zero up through you know all the indices we are gonna look to see if a of i is the max so how do we know i is the max well we'll start off assuming that it is and if we see anybody bigger then we'll assume if we failed okay um and so if after looking at all the other elements we know that this is the max then we're good so we know it is the max so we just do this for every element so we end up with this awkward little error here though in java which is it's saying that you need to return something here it's actually impossible for us to get to this point and re uh ever in a program so as it turns out here if you think about it if the length was zero we've already thrown an exception on line seven otherwise let's suppose we just have a single element well it'll never be properly greater than itself and so our single element would be the max okay so one thing we can do is is just say well we can do all this work here and then um we can move this the error is coming because java is not smart enough to figure out um that you can never get to line 14. so uh any case we can we can just reverse this so that we go ahead and do this uh loop at the top note that if the length is zero this loop will body will never execute um and we'll just immediately throw an exception so it's the equivalent code does it work let's try see if we got it right yeah okay cool so this is another way of doing the max and um some people would argue this is clear they're like yeah this makes sense to me i i get it um so what i'm doing is just looking at each element and determining whether or not it's the max and there's a question of like okay that's fine i mean is this as good as the other solution is one better than the other um there's not an obvious aesthetic reason perhaps i mean some people might say you know the problem with aesthetics is your beauty is in the eye of the polder so simplicity which one is simpler i don't know some people do think about the problem differently and so sometimes you can make an argument that you know this way of thinking about it made sense we're just going through and we're checking each element to see if it's the max and we eventually find one so what's wrong with that solution um seems fine so but in fact these solutions are not of equal quality and um to understand this we need to actually think about how long they take to accomplish what they're doing um so i'm going to use a different solution so we saw that this is correct so both these solutions are correct i'm not going to look at them in terms of correctness and i'm not going to look at them in terms of understandability both solutions are understandable but they have very different performance characteristics so let me first try the um the initial solution so this is my solution that we had initially using a while loop um so here we're just m is aggregating the max so far and if you run this what i'm going to do is run it and i'm going to run it many times okay but i'm not going to run it on small arrays i want to run them on fairly large arrays so my main program here is going to start at a minimum size of a thousand um and we're going to go up to about a billion if we get there so this is the underscore in numbers just makes them a little more readable that's a billion that's a thousand and my main program then is going to start a trial passing in the size and then it's going to run a loop where it starts with a 2000 sized array going up to the max up to a billion and each time we're going to be doubling in so in is doubled and what we're going to do is run the time trial again with a double sized array we just keep doing this with bigger and bigger and bigger arrays and what i'm going to do is just measure how long it takes to run the max function on an array of that size so to get an array of that size i'm using a class that's in your standard library it's called array generator it will just create arrays for us i'm going to use a particular one and we can talk about that choice in a sec so if you talk about it now if you think about the the solution we just went through it'll perform very well if the max is at the beginning of the array but it's going to do more work if the max is at the end of the array so i'm actually choosing a sorted array where the max is always going to be at the end so um we'll just see it is the worst thing we could do for that algorithm um okay but first we're going to try it on my initial bit of code and see what kind of performance we're getting so let's just run this and what it's printing out here is the size of the array that's in the absolute time it took this is the the in seconds how many uh how much time it took to do the max function and then the the ratio of this time to the previous time so um what's the the and um note that if an array is twice as big we would expect it to take about twice as long because we have to do about twice as much work um and in fact you can see this is born out here um for an array of um half a billion elements i'm taking half a second whereas for a quarter of a billion elements i'm taking a quarter of a second okay um and you can see that the ratio here is close to two note that there's a little bit of noise here and this is just because there's systems effects and other things running on your machine the noise is very noticeable when you're at small numbers small numbers essentially take no time and so in order to see these kind of performance differences you need to get large enough arrays where it's taking enough time that you can actually measure it in a meaningful way so you'll get noise like you know here four here you get one but as things get large enough usually you'll see some sort of pattern so this makes sense about twice as long for for twice for twice the size of the array let's try this other solution that we have as a candidate and see how it does so here's my solution where um it doesn't indent very nicely here so let's fix that okay this is the solution where we're um determining at each point whether or not we have found the maximum element so each one we're just checking it against all the others and let's see how it performs and oh this is very different um i believe i had what half half a billion in half a second and oh well i'm up at uh well 10 seconds just for 128 000 elements that's not great so this shows you the kind of performance hit you can get if you uh write code in an efficient way note that for for small values it probably doesn't matter here if i had a thousand elements in my array who cares it's going to take not very much time but by the time we're getting up to a raise of even you know less than a million this is a quarter quarter million i haven't even computed it yet you can guess how long you think it might take based on the kind of numbers you're seeing you can see it's about four times as long every time and indeed this is borne out so it took about 10 seconds to do 128 000 so it's going to take about 40 seconds to do 256 000 um so each for a rate twice as big it takes four times as long so if you remember your high school trigonometry what if you plot that function you're going to end up with a parabola quadratic equation this is quadratic growth in terms of time on an array and so this is an objective criterion where you can say oh this solution is worse in fact there were people that say this is not a solution at all this is a bug this is a bug that will show up at some point if you end up getting large enough input so so performance is an important measure or metric for determining the quality of code okay so in conclusion here when you're reading and writing programs you need to think incrementally we think in small steps that's how the computer works and so in order to program it we have to atomize our thinking down to these fine grain steps and this of course this is the key to being a programmer is being able to think in terms of making small amounts of progress we saw how to do that with loops in particular loops are very important for programming because almost all programming is done over repetitive tasks the way you think about loops is using invariance and they're sort of a key to understanding loops even if you're just using them implicitly they are the key to making progress as a programmer and finally performance really does matter so you we're not talking here about oh this is just a little faster a little sore now we're talking about dramatically different performance for two apparently sort of similar uh quality solutions so in this class we will be emphasizing the correctness of our solutions and the performance of our solutions 
00:00 Designing loops: start in the middle
03:34 Designing loops: how to stop
04:09 Designing loops: how to start
04:52 You don't always start at zero!
05:41 Designing loops: corner cases
09:06 Another solution
15:38 Using performance to compare the solutions
19:12 Observing a linear-time algorithm
20:44 Observing a quadratic-time algorithm

What does this function do? [2/21]

01
02
03
04
05
06
07
08
09
 
  public static int f (int x, int y, int z) {
    int m = x;

    if (m < y) { m = y; }

    if (m < z) { m = z; }

    return m;
  }

How do you know? [3/21]

01
02
03
04
05
06
07
08
09
 
  public static int f (int x, int y, int z) {
    int m = x;
    /* m == max(x) */
    if (m < y) { m = y; }

    if (m < z) { m = z; }

    return m;
  }

How do you know? [4/21]

01
02
03
04
05
06
07
08
09
 
  public static int f (int x, int y, int z) {
    int m = x;
    /* m == max(x) */
    if (m < y) { m = y; }
    /* m == max(x,y) */
    if (m < z) { m = z; }

    return m;
  }

How do you know? [5/21]

01
02
03
04
05
06
07
08
09
 
  public static int f (int x, int y, int z) {
    int m = x;
    /* m == max(x) */
    if (m < y) { m = y; }
    /* m == max(x,y) */
    if (m < z) { m = z; }
    /* m == max(x,y,z) */
    return m;
  }

You don't need the code! [6/21]

01
02
03
04
05
06
07
08
09
 
  public static int f (int x, int y, int z) {

    /* m == max(x) */

    /* m == max(x,y) */

    /* m == max(x,y,z) */
    return m;
  }

Manual Testing [7/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static int max (int x, int y, int z) {
    int m = x;
    if (m < y) { m = y; }
    if (m < z) { m = z; }
    return m;
  }
  public static void main (String[] args) { 
    StdOut.println (max(11, 21, 31));
    StdOut.println (max(11, 31, 21));
    StdOut.println (max(31, 11, 21));
  }
}

Manual testing does not scale.

Manual testing instills fear of change.

Automatic Testing [8/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static int max (int x, int y, int z) {
    int m = x;
    if (m < y) { m = z; }
    if (m < z) { m = z; }
    return m;
  }
  public static void testMax (int expected, int x, int y, int z) {
    int actual = max (x, y, z);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with arguments (%d,%d,%d)\n", expected, actual, x, y, z);
    }
  }
  public static void main (String[] args) { 
    testMax(31, 11, 21, 31);
    testMax(31, 11, 31, 21);
    testMax(31, 31, 11, 21);
    StdOut.println ("Finished tests");
  }
}

Passing tests are silent.

Failing tests print a meaningful message.

There are many frameworks for writing tests.

Using an array of length 3 [9/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    if (m < a[1]) { m = a[1]; }
    if (m < a[2]) { m = a[2]; }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    StdOut.println ("Finished tests");
  }
}

Using a loop [10/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    for (int i = 1; i < 3; i++) {
      if (m < a[i]) { m = a[i]; } 
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    StdOut.println ("Finished tests");
  }
}

3 is a magic number: it is completely arbitrary

Magic numbers are bad

Generalizing [11/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      if (m < a[i]) { m = a[i]; }
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    StdOut.println ("Finished tests");
  }
}

How do we know it's correct?

Loop invariant [12/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      /* m == max(a[0]...a[i-1]) */
      if (m < a[i]) { m = a[i]; }
    }
    /* m == max(a[0]...a[a.length-1]) */
    return m; 
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    StdOut.println ("Finished tests");
  }
}

A loop invariant is something that is true every time, before executing the body of the loop

What about the empty array?

A bad solution [13/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { return 0; }
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      if (m < a[i]) { m = a[i]; }
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    testMax(0,  new double[] { });
    StdOut.println ("Finished tests");
  }
}

0 is a magic number: it is completely arbitrary

Magic numbers are bad

Exceptions [14/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { throw new IllegalArgumentException(); }    
    double m = a[0];
    for (int i = 1; i < a.length; i++) {
      if (m < a[i]) { m = a[i]; }
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    try {
      max (new double[] { });
      StdOut.println ("max failed: Expecting [IllegalArgumentException] with argument [ ]");
    } catch (IllegalArgumentException e) { }
    StdOut.println ("Finished tests");
  }
}

Exceptions were created to solve this problem

Testing for an exception is interesting

Designing loops from scratch [15/21]

Usually, we design a loop from scratch, rather than adapting a solution for 3 elements

Lets try it for max

Lets work with the following example: 

new double { 21, 41, 31, 51, 11 }
                         ^

Suppose our loop has already looked at the first three numbers, and we are considering the fourth

Solution with while loop [16/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { throw new IllegalArgumentException(); }
    double m = a[0];
    int i = 1;
    while (i < a.length) {
      if (m < a[i]) { m = a[i]; }
      i += 1;
    }
    return m;
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    try {
      max (new double[] { });
      StdOut.println ("max failed: Expecting [IllegalArgumentException] with argument [ ]");
    } catch (IllegalArgumentException e) { }
    StdOut.println ("Finished tests");
  }
}

General rules for desiging loops [17/21]

Another way to compute max [18/21] 

new double { 21, 41, 31, 51, 11 }
                         ^

Suppose we know that the first three numbers are not the max

What do we need to do with the fourth number to make progress?

Another way to compute max [19/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    for (int i=0; i < a.length; i++) {
      boolean isMax = true;
      for (int j=0; j<a.length; j++)
        if (a[j] > a[i])
          isMax = false;
      if (isMax) return a[i];
    }
    throw new IllegalArgumentException(); 
  }
  public static void testMax (double expected, double[] a) {
    double actual = max (a);
    if (expected != actual) {
      StdOut.format ("max failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, java.util.Arrays.toString(a));
    }
  }
  public static void main (String[] args) { 
    testMax(31, new double[] { 11, 21, 31 });
    testMax(31, new double[] { 11, 31, 21 });
    testMax(31, new double[] { 31, 11, 21 });
    testMax(21, new double[] { 21, 11 });
    testMax(21, new double[] { 11, 21 });
    testMax(11, new double[] { 11 });
    try {
      max (new double[] { });
      StdOut.println ("max failed: Expecting [IllegalArgumentException] with argument [ ]");
    } catch (IllegalArgumentException e) { }
    StdOut.println ("Finished tests");
  }
}

Are these solutions of equal quality?

Using a timer [20/21]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
package algs11;
import stdlib.*;
public class PlaygroundMax {
  public static double max (double[] a) {
    if (a.length == 0) { throw new IllegalArgumentException(); }
    double m = a[0];
    int i = 1;
    while (i < a.length) {
      if (m < a[i]) { m = a[i]; }
      i += 1;
    }
    return m;
  }

  public static double timeTrial(int N) {
    double[] a = ArrayGenerator.doubleSortedUnique(N);
    Stopwatch s = new Stopwatch();
    max (a);
    return s.elapsedTime();
  }

  private static final int MIN =         1_000;
  private static final int MAX = 1_000_000_000;
  public static void main(String[] args) {
    double prev = timeTrial(MIN);
    for (int N = MIN*2; N<=MAX; N += N) {
      double time = timeTrial(N);
      StdOut.format("%10d %9.3f %5.1f\n", N, time, time/prev);
      prev = time;
    }
  }
}

Conclusions [21/21]

To read or write a program, we must think incrementally, in small steps

Loop invariants are useful

Performance matters

Revised: 2008/03/17 13:01