Today we're going to talk about a Java language construct, that's going to help us write programs that process large amounts of data, and it's very easy to use. It's called the array. So, we'll begin with some basic concepts about what arrays are. Now this is adding to our basic building blocks for programming, we're up through conditionals and loops, and our next construct that we're going to talk about today is arrays. What that does, is give us the ability to store and process huge amounts of data. We're going to see lots of applications throughout this course. Fortunately, this is a very natural and easy construct to use. It's our first data structure. What's a data structure? It's an arrangement of data that helps us efficiently process it in a program. An array is defined to be an index sequence of values of the same type. We'll take a look at what each of those ideas mean. So here's an example of an array, it's 52 playing cards in a deck. That's the example that we're going to work with for a lot of this lecture. So, some cards in the first position, other cards in the second position, the ace of hearts in the third position, and so forth. Given an index then we can immediately get to the card that's in that position in the deck. But there's many other ideas where you might use an array. So, you might have a lot of students in an online class, and again, you can get to each one quickly through an index. We're going to look at digital images. There might be a billion pixels in a digital image, and we want to be able to quickly get to each one of them. Or Biologists studying DNA, there might be nucleotides in the DNA strand. Many other examples showing that you've got data, elements of the same type, and you have a huge amount of them, and you need to structure them so that you can process them efficiently. So, our main purpose of the array is to facilitate the storage and the manipulation of this kind of data. So, what does it mean about processing many values of the same type? So here's an example that we could write after the first lecture without using arrays at all. In this case, maybe we have 10 items of data, and we just named them a zero through a nine. If we want to refer to the fifth one, we can say a4 equals 3.0, or the ninth one a8 equals 8.0, and so forth, and even use them in arithmetic expressions. Now, but after a while, you can see that it would be very tedious and error-prone to have code of this sort. A much simpler way to do it, is using an array. This is equivalent code using an array. Instead of declaring all those things of the same type separately, we just declare in one statement that we're going to make an array. We'll talk exactly about how those first two statements work in just a second. Then if we want to refer to the fifth one, we just put that index inside square brackets, or the eighth one whichever one we want, and we can use those that array name followed by an index in square brackets just the same way we use any other variable of that type. Since they're all the same type, the Java compiler can keep track of them and check the type. That's convenient enough with 10 values, but what this does immediately, is it scales say to a million values. We have a huge amount of data. It would be indeed tedious to give them each one of them a different name. With an array, we have the shorthand where we just use the brackets to refer to individual pieces of the data. It scales to handle huge amounts of data. So, what's an array look like in the memory of your computer? Well, since an array is sequence of values of the same type, it makes sense to take advantage of the fact that the computer's memory is also an index sequence of locations, and we might as well we'll talk about this in a lot more detail later on, but it's easy to think of the memory of the computer as just a long sequence of locations. We're going to store the array contiguously in memory. Since every type value for primitive types like double and int for now, it's going to occupy a fixed number of locations. However, depending on the type of the data, if we store the array values in contiguous locations, that gives us what we need in order to be able to do efficient processing. The critical idea is, well, we start indices at zero, and that's just a convention that makes the computation a little bit easier. But the real critical concept is, if we have i, then we can quickly access the value of A of i. Just have to know how big the thing is, multiply by i, add it to the memory address of the beginning, and then we're there. Now for simplicity in this lecture, we're going to write the array name with an arrow pointing to where it begins. So, thinking of the array name as the memory address of the first location. Actually, in Java, it's just a tiny bit more complicated, and we'll get to that at some point later in the class. Now one way to, immediately one really critical concept that derives from this, if you're using a name to refer to the array, if you make an assignment b equals a, you're making them point or refer to the same array, and we'll look at that in more detail later on, but it's important to point that out right at the outset. So, you might think that it would copy the array the way that we do with values of variables of a primitive type, but it doesn't. Okay. So, let's look at Java has some built-in language support for arrays. They're so useful. There are some aspects of the Java language that are built into directly support arrays. So, declare an array. We have to declare a variable. We have to declare its type. In this case, we have to declare that its an array, and then we have to declare the type of all the values. So double size it's an array of double values in the brackets say it's an array. Now, how did we create an array? For variables of primitive types, we don't actually have to create anything, but for an array, we have to tell the system that it's time to find the memory for that array. So, what we do is use the keyword new. That keyword new says create us a new array, double is again the type, and then inside the brackets is the length of the array. So this variable a has been declared to be an array of doubles, and then this statement here creates an array of different length, and then assigns that to a. Referred an array entry by index, we already went through that. You just use the array name, and then in brackets, and then you can put anything that evaluates to an int. Refer to the length of the array, you just say a.length. In lots of programs that we write, we want to be able to refer directly to the length of the array. Now, the most complicated thing is getting started, and so we'll look carefully at each of the ways that you might want to initialize an array. One of the important features of Java to remember is that it'll default initialize array elements to zero for numeric types like double or int, short, or long. So, if you say a equals new double a 1,000, you get a brand new array that are all doubles, and all initialized to 0.0. So, you don't have to write code like with a for loop assigning each array value the value 0.0. In many languages, you need to write code like that. In fact, most of the time, we declare, create, initialize in just one statement just to make the code more compact. So, this one just like we do with variables, this one says double brackets. A says, a is an array of doubles, and then the right-hand side says create a new one of size 1,000 and initialize them all to 0.0. Now it's important to remember this is a compact statement but it takes time proportional to the length of the array, because Java has to go through and initialize everything to zero. So, certain points will have to be cognizant of that fact. You can write a small amount of code that might take a long time because Java has to go through and initialize everything to zero. So that's the language support, and that's really all the code that you need to know in order to be able to write an interesting and effective code that uses arrays. One other thing initialized to literal values, you can write that X as an array of doubles and then you can put a bunch of values inside curly braces and it'll create an array of exactly that length and initialize the array with those values and that's useful for arrays that aren't long or large to get them to get started. Okay so that's the language support that we need. Now, let's talk about this idea of copying an array. Now, if we have an array that's got some values in it and maybe we need a copy of that array because we're going to perform some operation on it, but we still are going to need the original values later on. What you need to do is create a new array. So, in this case, we create a new array b. We declare that it's going to be an array of doubles and then on the left hand side and the equal side we create a new one, how big should the array b be? It should be the length of a. So, we put a.length inside the brackets, create a new array of doubles of a double length doubles. So, it'll get initialized to 0.0 Didn't write those in because we're going to overwrite them immediately. So, what we're going to do is, for i from 0 to a.length, we're just going to say b of i equals a of i. So, we just assign the first, one that's b of 0, b of 1 and so forth. We go through and explicitly copy every value from a into b and then once we've done that, we have a new array. Again, if you write the code b equals a, it doesn't do that, it just makes b and a refer to the same array. You can write b equals new double a.length and it'll do that, but then, if you say b equals a, it just resets b to be the same as a and forgets about that new array that it created, that's copying an array. So, here's some typical examples of programming with arrays. Actually, we've already used one and that is accessing the command line arguments. There's a system array called args that contains the command line arguments that you type and we'd been accessing those just by putting the first one, a zero inside brackets and so forth. So, we use that in our gambler's ruin simulation last time. Now, for all of this code just to keep it brief, we're going to assume that the variable N got sent to a.length and b.length. So, here's copying an array, that's the code that I just gave with that caveat. Here's an array code that creates an array with N random values. We create a new array a of doubles and of size N and then for i equals 0 to N, we just fill it with math.random, different double for each array entry. Printing the array entries one per line, that's something that we do inside a for loop. So, very often with a for loop, running through an index i and then using that index i to access the ith element of the array. We're going to look at more complicated code later on, this is just to get used to the idea of using arrays. This code here computes the average of array values. So, its initialized sum at zero, go through the array adding in each array element and then declared a double variable average and that sum divided by N. This is similarly finding the maximum, initialize a variable max at a of 0 and then for the rest of them, if you find a bigger one then current maximum then reset max. So, these are typical examples of simple computations that you might want to perform with arrays just to get you used to the idea of writing this code. So, here's a quick pop quiz, study this code and try to figure out what it's going to print. We make a new array a, b and then we go through N_b of i equals i and print out the two things. This is again just a quick test about copying, I hate to overemphasize, but everybody gets burned on this. After you say b equals a, b and a are referring to the same array. So, no matter what you do to a, you're going to do the same thing to that array to b, because it's the same array and so that when you print it out, you're going to get the same thing, they point to the same array. Okay. So, typical bugs when we program with arrays. So, one is array index out of bounds. So, when you define an array of say, size 10, it's only creating 10 elements starting at zero. So, the index must be between zero and nine. If the index is not between zero and nine, then you're going to get an array index out of bounds error. In this case, i goes to 10 and there's no 10 in this this particular code it should go from zero less than 10 and then it would get the 10 elements with the right indices. So, array index out of bounds, if it's negative, if it's bigger, the length are bigger then, it's going to be out of bounds. Here's another error that we all get. We say in the first line that a is a variable declared to be an array of type of doubles, but that's all we do, we never actually create the array. So, in this code, we'll buggy because their reference a of either the array never got created. So, get an error message on that. Or, the other the other extreme is forgetting to declare the array and just say well, a equals new double N, it should know that what a is, but in Java everything its type every variable's type has to be declared before it's used. So, a compiler doesn't know what type of data a refers to in order to check that you're doing what you wanted to do. So, that's typical bugs that we have to get through and you're encouraged to type these in and take a look at the error messages that you get when you try to compile this code. It's always a good idea to look for error messages under controlled conditions rather than trying to figure out what they are when they happened to you unexpectedly. So, that's the basics on programming with arrays.
