ProgrammingMethodology-Lecture17.pdf

Programming Methodology-Lecture17

Instructor (Mehran Sahami): All right. So welcome back to yet another fun filled

exciting day of cs106a. A couple quick announcements before we start. First of which,

there is one handout, which is kind of a quick reference for you on ArrayLists. It’s sort of

all the ArrayLists you need to know for the hangman assignment part three. If you

haven’t already done it, now you have a quickie reference for it. If you’ve already done

it, you don’t need the quickie reference, but presumably, you saw everything you needed

already in the textbook or what we did last time in class. The midterms, it was just a

rocking and rolling good time. If you weren’t there [inaudible], but two things, if you

took the exam, please don’t talk to other people about the exam because there are still

some people left to take the alternate exam; and if you’re taking the alternate exam, you

missed out. You’ll still take the alternate exam, so you’ll get the exam, you just won’t get

the full effect of the exam under earthquake conditions, but thanks for actually just – it

was amazing, it was just like how many people want to continue and everyone was, like,

rock on. So thanks for continuing with taking the exam. I’m glad you made it through just

fine. Last thing, a little contest. I’m glad to see there was other people besides us – we

were a little worried it was gonna be like me and 300 normally dressed people, this is not

what I normally dress in around the house, just when I’m in meetings on campus. So the

real question is who am I? Anyone know? It’s a very specific person. Not King Arthur.

What? Student: Sir Lancelot.

Instructor (Mehran Sahami): Not Lancelot. Student: [Inaudible]

Instructor (Mehran Sahami): I almost considered Karel. I almost went for Karel. I got

the big box, but it’s kind of hard to draw, sort of like, Karel cannot draw that much in the

big box. No. Well, I’ll give you hints as we kind of go along, and at the very end I’ll

show you if you can’t figure it out. I almost considered giving whoever could figure it out

a 100 on the midterm, but I figured that was kind of just a [inaudible] way of giving you a

100 on the midterm, so I’ll just give you lots of candy. So anyway, just think about it, and

if you want to try to search the web or whatever, it is a one particular character, and it’s

not a wizard. I actually thought, “Oh, I could just make it easy for you and just come in

and be, like, oh, ha, ha,” because most people, without the hat, would see it and they’d

go, “Oh, you’re a wizard, right?” No. So I just brought the hat to kind of fool you. All

right. So with that said, time to actually wrap up one of our last topics, which was arrays.

We’ll look at a few more advanced things we can do with the arrays and then get into the

details of our next great topic, which is our friend the ArrayList. So when we talked about

arrays, a couple people last time said, “Hey, Miron, can I have multi–dimensional arrays,

can I have arrays that have more than one index, and in fact, you can. We do refer to

these things as multi-dimensional arrays. And so one way you might want to do it is let’s

say you wanted to have this dreaded thing called a matrix. How many people know what

a matrix is? I’m not talking about the bad movie. Actually, it was a good movie. The

sequels, not so great.

It’s basically just a grid of information. It’s a grid mostly of numbers if you want to think

about it in a mathematical sense, but really we think of this thing as a two-dimensional

array. And so the way you can think about is if I have a matrix that’s a [2] [3] matrix

what that means is it’s a grid that has two rows and three columns. Okay. And you might

look at that and say, “Hey, that almost likes an array, it looks like two arrays stacked on

top of each other,” and in fact, you would be correct. If we have multi-dimensional

arrays, what we’re actually creating our arrays of arrays. So really what we want to do

here, if we want to create this thing called a matrix, is we specify the type that we’re

gonna store in all of the boxes in that grid, and then we specify as many pairs of square

brackets as we have dimensions of that thing. So if we have two dimensions here like we

have rows and columns then we specify two open and closed brackets in a row, if we had

three like we wanted to make a little thing that represented a cube we’d have three sets of

brackets. So here I’m just having two because I’m just gonna show you two arrays so you

can think about the generalization from there. And then we give it a name so we might

call this thing a matrix. And then we specify basically the creation of that matrix in the

same way we created an array except now we have more than one dimension, so here we

say new, we specify the type again, like, indices and then to give it the size rather than

just having one size that we specify, we have a size for every dimension. So if this things

gonna be [2] [3], we specify the first dimension as two and then the second dimension as

three. And each one of these is its own pair of square brackets. We don’t use comma

notations, so if you’ve worked with some other language or you say 2, 3, nuh uh. It

doesn’t work in java. It’s [2] [3] no spaces immediately after it. And so what this does

when you create that is it sort of creates this thing that’s this grid that’s a [2] [3] grid. And

now you can refer to the individual elements of that grid, so the way you can think about

it is this is element [0] [0] or really you want to think of them in brackets, and then this

becomes element [0] [1] and this is element [0] [2] and so forth, so this is element [1] [0]

and this is [1] [1] and this is [1] [2]. So if you kind of think about assigning to elements

of that you could say something like matrix [0] [1] = 5 and what that will do is it’ll say,

“Oh, where is [0] [1], here is [0] [1].”

Well, what I’m gonna do is, in that particular cell in your grid, is just gonna stick in the

value five. And you can use that like an integer anywhere else you could use it like an

integer or a single element of an array. Okay. The other thing that’s kind of funky about

this is that this two-dimensional array is really – the way you can think of it is it’s an

array of arrays, right? It’s an array – think of it this way as an array. It has two entries in

it and what is each one of those entries of the array, well, really every entry of the array

you can think of this as one cell, that whole thing, and this whole thing as another cell

and each entry of that first dimension of the array is just another array with three

elements in it. Okay? So what that allows you to do is say something like matrix subzero

and matrix subzero, the type of this thing, is an integer array. A single dimensional array

because what is matrix subzero, it’s this full line here. It’s the first row of the entire

matrix, and then if I specify something else, like I specify a column, that’s how I get [0]

[1]. First I specify the row, and then I specify the column. If I don’t specify a column this

is referring to the whole row, which means it’s just referring to a whole array.

Student: Can you refer to [inaudible]

Instructor (Mehran Sahami): You can’t. You have to refer to things in order, so there’s

no way to just pull out a column, so if you’re feeling sort of like, “Oh, but in my Math 53

class we do all this stuff with columns.” Yeah. You just have to pick, in some sense,

what’s gonna be your major ordering for this thing and have that one be first. So you

could kind of think of it in your head that, “Oh, well, my first index is really my columns

and think of this thing as being the transposed and all that,” but you just have to keep

track of it in your head. Okay? Any questions about that? All right. So we can write a

little code that makes use of this just so you see a quickie example. And we could, for

example, go through all the elements of this grid and set our initial values to be one, so

we could have something like I = 0. “I” is less than – what you want “I” to be less than in

the first index is 2. I ++ and then you’re gonna have some other four loop. Let’s say this

is J = 0, J is less than 3 because that’s the size of my second index, J++. And then inside

here I could just say something like matrix I sub I, sub J = 1. And that would initialize all

the cells in my grid to be one. Okay? Is there any questions about that? Hopefully fairly

straightforward kind of stuff. You can have as many dimensions of arrays as you want

sort of within reason, and within reason being how much memory your computer has

right because if you imagine, “Hey, I don’t only want a [2] [3] matrix, I want a [2] [3] bi-

hundred matrix,” so this becomes a three dimensional array. Right? So I basically have

this grid repeated a hundred times going forward. Suddenly, you’re using up a whole

bunch of memory. Right? So you want to be careful doing that, but if you wanted to do

that you would just add another pair of brackets here and you’d add another pair of

brackets over here with a hundred and now you would have a three dimensional array. So

if you want to create, like, your friend the Rubik’s Cube or something, with is [3] [3] [3],

now you know how. Okay? And if you want to do real funky things with four and five

dimensional objects or whatever, be my guest. Okay? But we’re not gonna use them a

whole bunch in this class, so I might show you some examples of two “D” stuff

momentarily, but most of the arrays we’re gonna deal with are just what we refer to as

one dimensional arrays, right, which is just a list. All right? So any questions about multi-

dimensional arrays? If you’re feeling okay with multi-dimensional arrays nod your head.

Good times. All right.

So moving on from the array we can now go back to our friend that I briefly introduced

last time, and now we can go into excruciating detail, our friend the ArrayList. Okay?

And the ArrayList – the way you can think about is it’s an array just kind of cooler.

Okay? So the idea behind an ArrayList is an ArrayList first of all really is an object, and

it’s an object that’s provided for you in the Java Util Package. We talked a little about

this last time. I’m just repeating it just for good measure. So you import the Java Util

that’s star packet to be able to get at the ArrayList class. Okay? And the way you can

think about an ArrayList is it’s really like an array, except it’s an array that dynamically

changes its size depending on how you add elements to it. So you can just say, “Hey, add

another element to the end,” and it will just go, “Hey, you know what, I’ll just create

extra elements at the end for you and now your size is one greater.” And so the way to

think about it is in terms of effective and actual size, that we talked about last time, was

with regular arrays you set up with the actual sizes that’s declared, and then your

effective size is how much of it that you’re using. With an ArrayList, think of it as the

effective size and the actual size, at least stylistically, are exactly the same thing.

Whenever you want to add another element to the end, its effective and actual size both

grow. Okay? Now underneath the hood, the implementation actually involves some stuff

where the effective and actual size can be different, but that’s all abstracted way for you.

As far as you’re concerned, effective and actual sizes are basically the same thing. Okay?

And it provides some other functionality that is nice, and I will show you that in just a

moment. But this particular ArrayList thing is called a template. I’ll give you a little

history of templates. I mentioned this briefly last time, but I will mention it again.

Starting in Java, the book refers to it as Java 5.0. A lot of programmers will say Java 5.0.

Some programmers will say Java 1.5, and what you have installed on your computer is

either Java 1.5 or Java 1.6, which some programmers would say is either Java 5 or Java 6,

which you would look at and say, “Hey, man, that makes no sense at all, why is it like

that?”

So I’ll give you a little bit of history. Quick history lesson for the day. Many years ago,

oh about 1995, there was this thing called Java 1.0. It came out, people were happy and

went, “Oh, nice,” and then Java 1.1 came out and people looked at that and said, “Yeah,

nice,” and then Java 1.2 came out and people said, “Nice!.” So when they said, “Nice!,”

1.2 in some people’s mind was such a major change in the language Java that they started

calling it 2.0, and at that point when 1.3 comes out you can’t say, “Oh, well, that’s 2.1,”

right, because then it gets really confusing so then when 1.3 came out people called that

Java 3.0. And 1.4 was 4.0, 1.5 became 5.0, 1.6 became 6.0, but in fact, the confusion still

exists so if you go and look in your system most of you on your system it will actually

have this 1.X number. Most programmers will actually refer to it by just the X as opposed

to the 1.X. Don’t be confused. They’re really referring to the same thing. Okay? So what

we’re dealing with here, in terms of ArrayLists as templates, is Java 5.0 or later so

sometimes that’s just written as 5.0 plus, which all of you should have because that’s

what you installed in the beginning of class. The book actually shows both the pre-5.0

and the post 5.0 version. We’re just gonna deal with the post 5.0 because at this point, the

older version is just not worth worrying about. Okay? So what is this thing called a

template that exists in Java 5.0 and later versions? Okay. What a template is is it’s

basically a class that allows you to specialize it based on the type. What does that mean?

Okay. So let me give you a few examples of what that actually means. What that means

is when you see methods for this ArrayList class, and you’ll see them listed in the book,

you’ll see something that looks like this. There’s a method called Add and it returns a

bullion and you’re like, “Oh, that’s all good and well,” what kind of parameter does Add

take and you’ll see the spunky thing that looks like this, [T] element, and you look at that

and say, “Oh, Miron, you never told me about the [T] type, what type is that?” And the

way you can think about it is this is a parameterized type. When you create an ArrayList

you say, “I’m gonna create an ArrayList of a particular type.” So when you set up your

ArrayList you create an ArrayList object. And when you create that object, as you saw

last time very briefly, in angle brackets, which are actually less than and great than signs,

you specify a type like string. So you say ArrayList string and we call this thing, for

example, SList and we might create that to be a new ArrayList. Again, we specify the

type string () because we’re actually calling the constructor which takes no arguments.

Okay? So you create this new ArrayList and this thing that you specify here, the type that

you specify there, is what we refer to as the type or the template.

You can think of the template as having all these holes in it, and the way those holes get

filled in is they get filled in with whatever type you give it here. And those holes are

specified by this [T]. The way you can think of this T is it’s the Type, that’s why it’s a T

that this template is what we refer to instantiated as. You create one of these templates of

this type. So I create an ArrayList of strings is the way programmers refer to it. Usually,

you can think of this as meaning of and this as meaning nothing. So ArrayList of string is

how we would actually say it. And when you create an ArrayList of string you get an

Add method for this ArrayList of strings that’s now [T] is replaced by string. So the

method that it actually provides for you is an ad method that takes a string type. Okay? If

I were to create an ArrayList of G ovals I would have an Add method for that class that’s

elements was a G oval. Okay? So it creates for you basically a whole class that has all the

holes filled in with whatever type you specify here. Any questions about that? Kind of a

critical concept, new in Java 5.0. It’s new, it’s dynamic, it’s cool, it’s funky. People like

it, now you can, too. All right. So let me show you some of the methods that you get with

this ArrayList kind of thing, and then we’ll actually go into the details of using it. And

you’ll notice that when we talk about the methods, this [T] thing will show up all over the

place. And the way you want to think about that is this is just getting replaced with

whatever type you instantiate your ArrayList to be. So if we go to the computer real

quick, drum roll please, it’s the methods of the ArrayList. So what are the methods of the

ArrayList? The first two methods are Add. What Add does is it takes in some element

type of whatever type your ArrayList is instantiated to be, right, the [T] and it adds it to

the end of the ArrayList. And you might say, “Hey, Miron, what does that return a

bouillon,” and it always returns true for the bouillon, so why does it return a bouillon at

all? And about in a week it’ll be clear why it always returns a bouillon. Okay? And why,

in this case, it’s always true, but as far as you’re concerned you don’t really care about

the return type. You’re not gonna do anything with it because it’s always true. You’re

just gonna say Add and even though it’s returning something to you, you’re not gonna

[inaudible]. It just adds an element to the end of the ArrayList, which means the

ArrayList dynamically grows by one. Right? It’s an array with dynamic size, so it just

creates the space for you and adds the new elements to the end. You can also add in a

particular position just like you could add an array at a particular position, you can do

that in an array list by specifying the index and the element that you want to enter at that

index, and it will just put that element in at that index for you and it’s just kind of all

abstracted in terms of how it does that. Okay? It’s just growing its size as needed. Besides

adding things you can remove from the ArrayList, right, which is something that’s funky.

You didn’t really think about removing from an array. Right? An array you could sort of

say, “Yeah, read that value and maybe I don’t care about the value anymore,” but you

couldn’t actually say, “Yeah, just get rid of that value completely, like, get rid of the

space associated with that value.” Okay? So when you say remove at a particular index, it

actually removes that element and returns it to you from the ArrayList.

And similarly, you can either remove or you give it an index and you say, “Give me back

that particular element,” or you can remove a particular element if it appears. So this

returns a bouillon. So let’s say you have an ArrayList of strings and one of your strings

may be cs106a, and you’re like, “Oh, cs106a, it was so near and dear to my heart until I

had to take a midterm in the middle of an earthquake,” remove cs106a. And then you try

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: