cs046 ยป

Contents

Arrays

We've been talking about array lists up to now and array lists are very flexible, but there are times when arrays are lower level construct are more useful. Here is how to make an array of values of type double. As you can see, it looks quite different than the declaration of an array list, so let's take it apart. Over here is the type, it's an array indicated by these brackets of double. This is the variable. Here's the new operator and back here we say we want to construct an array of ten doubles, so as you can see you put the length of the array inside the brackets, unlike with arrayLists, the size of an array can never change, this array here has been made with ten numbers and it'll always have ten numbers in it. No more and no less. There's a second way of constructing an array that's often very convenient. Here I have again an array of floating point numbers. I call it moreValues. And over here I simply put enclosed inside braces the values that I want to put in the array. This array has length five and again it'll always have length five.

Array Elements

Let's see how we can access the individual array elements. With arrays, you don't call a method to get at an element. Remember with an array list we would have called .get, but with an array you use the brackets and you put the index inside. The values bracket zero, is the equivalent of calling values, dot get zero. For an array you use the brackets. For an array list, you use a method. You use the same notation if you want to store something, into an array. So here values bracket zero equals 42 means put the number 42 into the zero slot of this array. That's a little simpler than with array lists where we would have had to call .set(0,42). How can we look at all of the elements of an array? That's very similar as with array lists. Here we have a for loop. We want to look at values bracket i and i goes from zero to one less than the length of the array. With an array list we would have called dot size. Note that length does not have parentheses. That's just an oddity for historical reasons. We simply looked at all of the elements in the array, and as with an array list, we can use an enhanced for loop to make this a little simpler. Here's the equivalent enhanced for loop, over here is our array. We want value to assume each of the elements in turn, and then we use it. Note that with the enhance for loop, you cant tell any difference between an array and an array list. You put the array, array list to the right of the colon, and the variable to the left of the colon gets assigned each element in term.

First Five Primes

It's nice that array syntax is so compact, but it has a lot of punctuation to memorize, for practice how would you declare an array containing the first five primes in one line, and the first five primes are 2, 3, 5, 7 and 11. Put your code here.

First Five Primes

Here's the answer. The type of an array is always the type of the items that it contains followed by square brackets. I named this one primes, and to build the array itself, I used curly braces and separate all of the items by commas.

Modifying the Array

If we declare primes as we just did, and then run this for loop, what will primes contain? Separate items with commas.

Modifying the Array

The answer is two, three, five, three, two we start out with i as zero so primes four takes on the value of prime zero, so 11 is replaced with two, now we go through again but this time i is one. So we look at primes three, and fill it with the values from primes one. So seven is replaced with three. And i would be two, so we break out of the loop.

Put 10 in the First and Last Spaces

If I declare an array values and initialize it with new int 10. Write statements that put the value 10 into the spots with the lowest index and the highest index. So, if this was your array, put 10 here and here.

Put 10 in the First and Last Spaces

The most robust way to do this would be to set the 0 value to 10, and then to set the last value to 10 use values.length and subtract 1. Instead of writing values of values.length minus 1 we could have written values of 9 equals 10. This is a good answer too but it will only work if the array has exactly ten elements in it. This one will work for any size of array

Array of Strings

Let's practice a couple more declarations. How would you declare an array of strings, with space for 10 values? How would you declare an array of strings, that contains two values? Yes, and no.

Array of Strings

To declare an array of strings with space for ten values, we would make the variable and give it a type of string array and an initial value of a new string array with space for ten items, to declare an array of strings that contains two values, yes and no, we use the curly brace notation, the type is the same as before but now we put yes and no. But now we put the strings yes and no in the curly braces separtated by commas.

Enhanced For Loop

Some loops are better written with an enhanced for loop, and some are better left alone. Here are three different for loops, the first one, the second one and the third one. Check the box for the for loops that might be better written with an enhanced for loop.

Enhanced For Loop

The answer is, the first one can be written as an enhanced for loop. These other two would require lots of extra counting variables and things to make them work that way. This one would be difficult to write as an enhanced for loop because it's using the index i to calculate a value, it's also changing the values stored in the array. Both of those things are harder to do with an enhanced for loop. This one would be hard to do with an enhanced for loop, because it's not actually looking at all of the values in order. It starts at Index one, and while looking at any one index, it's also looking at the last index. In an enhanced for loop, you will only get one at a time, and would have to do some fancy trick to remember the last one that you'd seen. This way is much simpler.

Arrays or ArrayLists

So we have arrays and we have array lists. And it's a bit of a nuisance that we have both, because it means we have to make a decision between them whenever we want to collect elements. Generally, array lists are more convenient, because they can grow and shrink. But there are a few reasons why you might want to prefer arrays. First off, the syntax with the brackets is more compact. For example here we assign values one to values two. And that's a bit easier to read than the equivalent with array lists, which you see over here. Also, if you know exactly what values you want in a collection, then arrays give you an easier syntax. Here, I have a string of workdays, and I know exactly that I want these five strings, no more, no less, I know what they are. Then I can use, this handy syntax, to construct an array, and initialize it right away. With an array list, I would have to call the add method, five times. Once for each of these strings. Another disadvanged of array lists, is that they don't work well with numbers. We have never done that so far. But let's say we wanted to collect numbers in an array list. I'd have to do something like this and when you look carefully you'll notice that the double here has an uppercase D. Normally when we want to have a floating point number, we write double with a lowercase d. And you may recall that the number types are not classes in Java, but inside, the angle brackets here, I must put in a class. An ArrayList can only collect objects of a class. So, for every number type, there is a companion class, called the wrapper class, and an object of a wrapper just has some number inside. If you have lots of numbers, say for the sake of the argument, you have a million values, it takes a lot more space to store a million wrappers each of which contains a number than it would be to use an array that contains the numbers directly. Most of the time we're not that concerned about efficiency but when you are in need to collect a lot of numbers, definitely use an array. In conclusion, you use an array list (no period) As a rule of thumb unless you want the nice syntax that in the array gives you, you're having the brackets, having the initializers or you collect lots of numbers in that case Array Lists are quite inefficient, so arrays to have their place and [UNKNOWN] have some practise questions prepared for you

Partially Filled Arrays

One challenege when using arrays is that the length is fixed. So let's say that you need to collect some numbers, and you don't quite know how many, you're going to have to make an array that's large enough to hold them all, but then you may have fewer numbers in the array than it can hold. We say such an array is partially filled. Just like this beaker over here, you wouldn't want it to be filled up all the way to the rim. And in this situation, you need to keep track of two things. You need, the, overall length of the array. So, here I'll assume I'll never have more than a 1000 numbers. I allocate my array to have, this length, and then I keep a companion variable, that I call the size. That tells me how many elements I currently have. Right now I don't have any. Whenever I need to insert a new element I execute this code here. I move the new value into values and bracket size. And then I increment the size. For example, to insert the very first element, size is 0, values[0] is now initialized, and the size becomes 1. Next time, values of 1 gets filled. And so on. Now what happens, if I fill up, the array with a 1000 values, and then want to add the 1000 and first? Let's have a look at that situation. So here I have my partially filled beaker. I fill in more and more. And eventually when it gets full, what choice do I have? I have to get a bigger one, and pour everything into that. It's the same with partially filled arrays. So here's my array. It's almost full, now it's completely full. I'd like to add another element. So I get myself an array that's twice as long, copy over all the values. And now I can forget about the old array, and insert my next element. Over here, of course one can program that by hand but as it happens there's a library function that does the work for us. Here it is. The copy of function takes an array and then the desired length of the larger array, it then makes a larger array and copies the original one in there, returns the larger array and we just capture it here again. So that's what you'd have to do. If you're ever faced with a situation where you want to collect an arbitrary number of values. It's that kind of thing that makes you appreciate the array lists where you never have to worry about growing an array.

Homework Scores

A lot of teachers have to add up all their students scores to calculate final grades. When I was in middle school a lot of my teachers had a paper grade book, but by putting scores into a computer, teachers might save themselves some work. We're going to build a HomeworkScores class that will read all of the scores for one student and give useful summaries of their work. Eventually it will be able to calculate the total and average scores, and drop the lowest. But first it needs to read the scores for one student. I started the class for you. It'll save the scores in an array of doubles, which will be partially filled. We'll allow the teacher to enter whatever number of scores they feel like. Let's not worry about re-sizing for right now, we'll just make the array very big to start with. Before I ask you to implement the readScores method I want to show you one more thing that's going to help.

Homework Scores Continued

I want you to look at the toString method that I added to this class. You can use toString to print out all of the scores. It might help if you find that you need to debug a bit. It's also worth spending a moment to look at this carefully. The arrays class has a lot of useful methods for working with arrays. It's structured a little bit like the math class. So to use these methods you call Arrays.toString or Arrays.copyOf. Now, if I call Arrays.toString, and I just gave it the scores, which is a partially filled array, it would print out a whole lot of zeroes at the end. And I'm not really couting those as part of my array right now. So I need to trim down the array first. I'm using Arrays.copyOf, to trim down the array. Arrays.copyOf takes the array that you want to copy and the desired new length. So this method call makes a shorter array that is a copy of the original and then when I pass that to arrays toString it will now return a string representation of only the part of scores that i am interested in

Read Scores

Now, it's your turn to add some code to the homework scores class. The read scores method takes in a scanner and that should use this scanner to read and enter the values. Keep reading scores until the user enters a Q.

Read Scores

To implement this method, we'll use the same kind of while loop, we learned, in lesson four. To keep collecting doubles, as long as the user enters doubles. Inside the loop, we'll read that double, using the scanner that was passed in, and then we'll save it. We want to save it in the next open spot in scores, which should be at index, currentSize. So we will put nextScore in there, now there is an new element in scores so the size has changed, we'll need to increment current size to reflect that, lets see it in action, lets see it in action, if I run the demo and enter some scores it saved to the scores in the order that I've entered them, looks like we are ready to add another feature

Sum Scores

The next method you'll want to add to the homework scores class is sumScores. How would you implement this method?

Sum Scores

There are a couple of possibilites here. We're working with a partially filled array so do we want to use an enhacned for loop or regular for loop? If we used the enhanced for loop it'll ad up every single item even ones in the part of the array that we've said is empty. And we know that the current size is four but the enhanced for loop. Just knows the actual, just knows how much space there is in the whole array. In this in this case, the enhanced for loop will work, but only because the array was initialized full of zeros. So when we take the sum and add all of these zeros, it wont actually give us the wrong answer. But if I were dealing with an array that might have extra junk left over in the empty space, I would probably want to use a regular for loop. and only go up to the current size of four. I will show you both of these, either way I need my sum that's starts with zero and I will return that sum at the end. If I use the enhanced for loop i just increment the sum by score each time, and that should work. But i am nervous that might be other junk left over the end of array, then I would declare a loop counter variable and stop before it gets up to current size, and look at each item one at a time. And here, I would have to get the item out of scores, because I, and here, I would have to get the item out of scores, because I'm not using an enhanced for loop anymore. I should probably actually give my [LAUGH] loop counter variable an initial value. Now we can see this in action. If I run the demo and enter their scores, I get their total.

Average Scores

Now let's look at average score. If all the homework scores are out of the same number, their average homework score might be much more helpful than their total score. Can you implement this method?

Average Scores

To return the average score, I want to calculate the total, and divide by the number of scores. I already have a method to calculate the total. I can call some scores, and divide by current size. But I'm not sure that this is what I want to return. We had that issue before, where if current size was zero, we ran into errors. So I'll need to handle that case. If the current size is zero, I want to return zero, otherwise, it's safe to calculate the actual average. We need to actually return the average. Compile. And now, if I enter the scores that I entered before, I'll get the total, and also the average. But what if I wanted to remove the lowest score? We haven't talked about removing items from a partially filled array, yet. Kai will talk about that, now.

Inserting and Removing Arrays

Now we want to see how to insert an element, here is my partially filled array. And I want to insert an element before this position. So I need to move all of these elements out of the way, so that the green element can go into the slot. Now, you have to be a bit careful with the move out of the way part. If I were to move this element over here, and then this element over here and so on. That will be bad because then this element would override the next one before I had a chance to move that one out of the way. So, in other words, this element would flood the entire tail of the array. The remedy is to do the movement starting at the end of the array. So, I first move this one, then it's predecessor, then it's predecessor. And I keep going until I've moved the one into who's slot that I want to put the new one. The other thing to remember is that insertion increases the size, so I have to make sure to add one to size of my partially filled array. Le'ts look at this in Java code. I increase the size. Here is the loop to make room for the new element. So when I increase my size then I am starting at size minus 1, which is same as the old size. I now go backwards. And each of the moves goes the other direction than the one that you've seen with removal. It goes from a lower index to a higher index. And the last movement is the one that moves pos to pos plus 1, so we want this one to be pos, which means we want I to be plus, plus one and that's where we stop. Finally, when we're all done, we can insert the new value after position pos. As you have seen inserting and removing array elements requires quite a bit of movement. You need to move elements out of the way, in the case of insertion, or move them to close up the gap in the situation of removal. It was also easy with the array list, where you just called add and removed. But the reason that, as explained to you, what actually goes on with arrays, is an array list has a partially filled array inside it, and it's sometimes important to know which operations are cheap, and which ones are expensive. And sorting and removing can be expensive for a long array.

Inserting and Removing Arrays Continued

Do you remember how we used the add and remove operation awhile ago to rearrange images in the gallery? We removed the last element and added it before the first one. Now that you know how removal and adding works in Java code I'd like you to tell me Tthe cost of this operation. How any elements were visited in the process? With visiting I mean, how many elements were read and how many were modified. So count every read and every write and tell me the total number of visits.

Inserting and Removing Arrays Continued

There were a total of ten visits. Let's count them. We removed the last element, we had to read the element for that purpose, but there was no gap to be closed up, because that was the last one. Now before we can insert it at the beginning, we have to move these four elements out of the way. Each of those moves involves reading the element and writing it back to the next position. That's two visits per element and there were four elements to be moved. And finally the removed element has to be written back to the location zero. That's one more visit for a total of ten visits. The point that I want to make is that insertion into an array list. Doesn't work by magic. Under the hood, the other elements do get moved out of the way. Now you've seen quite a few algorithms for arrays and array lists, and many times you can solve your problems by just using one of those existing algorithms. But there are also situations where you need to understand the algorithm so that you can adapt them to new situations. Sarah's going to give you an example where you have to do just that.

Removing Lowest Score

You can combine basic array algorithms to perform more complicated tasks. For example, we can calculate the final score, which is the sum of all the scores except the lowest one. This is related to several of the algorithms that you've just seen. Let's write a method to drop the lowest score, and I'll give you some methods that you can use. One removes the score at a particular index. One finds what the minimum score is and one finds the index of a given score. Skip to the quiz and code up remove lowest if you're pretty sure you've got this. I'm going to do a demo on a small data set in case you want a little more info first. Let's say our set of scores was eight, seven, eight point five, nine point five, seven, four and ten. We'd also have some zeros left over at the end of the arrays since it's paritially filled, but current size will tell us not to go past there, I'd first find the lowest score, it might be 8, but 7 is better, it's not 8.5 or 9.5, there is 7 again, okay 4 is better not 10, okay so I'll go through again this time looking for the number four and remembering the index. And it looks like I found it, the index I want, is five, now, I remove the fifth element, which will move ten down and I'll need to decrease current size. You won't actually have to implement remove. But now you can see why it might be important when you're calculating the sum, to only look at the items that you know are in the array. Because this ten will show up in two places now. And you wouldn't want to add 10 to the sum twice. If you already have methods to remove, and to find a minimum element and to find a location of a given element, how would you code remove lowest?

Removing Lowest Score

The first thing I want to do is figure out what the lowest score is. The methods I have available are find, lowScore and remove. So first I want to find what the lowScore is. I'll call lowScore and put the result in a double. I'll call lowScore and put the result into a variable of type double. Then I'll find the exact location of that score that I know is the lowest. By using the find method. And then once I know where it is, I can remove it using remove. Now that we've implemented remove lowest, a user of the homework scores class could call remove lowest before calculating the sum or average of the final grade.

Find Lowest Scoring Position

Implementing remove lowest this way was nice because we already had these methods and we could just use them. And this almost reads like a kind of English now. What's the low score, find the low score, remove the low score. But these first two steps were kind of repetitive. In this example we had to go through every item to find what the lowest one was. And then go through them again to find the index of it. If this were a very long array with millions of items in it, we wouldn't want to have to go through all of the data twice just to get the location. We would want to think a little deeper and try to combine some of these loops. So, what if we had a method, getlowScorePosition, that would replace the two steps of finding the minimum element and also finding it's index.

Find Lowest Scoring Position

This looks better, but it won't work yet. First, you'll need to implement getLowScorePosition. Implement it so that it only looks through the data once. And remembers the position of the low score, as well as the score itself. To implement getLowScoreIndex, we'll follow the algorithim we talked about earlier, for finding the first portrait in the picture gallery. But this time, we're using it on a partially filled array, instead of an ArrayList. So we have to be more careful. We'll start by assuming that the lowest score, is the first one. Then we'll look at all of the items, starting at one, because we already looked at zero. Now for each of those elemlents, we'll compare it to the lowest score, and if it's smaller, we changed what we think the lowest score is. Now, while we're looking for the lowest score, we also need to look for its index. So, initially we assumed that the lowest score index was zero, and when we find a lower score, we'll update the lowest score index to be the index of that score. Now, when we finish looking at everything, the lowest score index that we found so far will be the overall lowest score index. Now that I have this method, the simpler version of removing the minimum score will work. I'll test it so I can be sure. And it looks like it correctly dropped one of the fives.

Can We Streamline More

So we just saved our computer program one pass over the entire array. Could we do this even faster? Could we do it without looking at every single item in the array? Take a moment to think. Imagine that there's one score that you don't read. What if that score was the min? If you don't read it, you can't find out whether it's the minimum or not. We can't find the minimum without looking at every score. In computer science we would say that we have to do a linear search. Now what if we knew something more about the elements in this array. For example what if I knew that all of the elements were sorted from lowest to highest. Then you wouldn't have to search the whole array to find the minimum. You would know that it was in the first position. As you continue programming, you'll learn how to organize your data so you can get the information you need as quickly as possible. But right now, let's talk more about discovering algorithms. Back to you, Kai.