Programming Methodology-Lecture24
Instructor (Mehran Sahami): So welcome back! So yet another fun-filled, exciting day
of 26A. After the break, it almost feels like – I came into the office this morning, not that
I wasn’t in the office during the entire break, but I came into the office this morning and
it felt like a new quarter had started. And I was like, oh, it’s been a whole week. And I’m
sure for you, it feels like you just wish a new quarter was starting because we still have
two weeks left.
So a couple quick announcements before we get into things. One is there is one handout,
which is your section handout for this week. And kind of one of the themes of this week
is bigness. In some sense writing bigger programs, bigger data structures, that’s the whole
deal. And we’ll kind of talk about that as we go along.
Another quick announcement, just wondering how many people tried the Name Surfer
demo online and had a problem with it? You folks, yeah, we updated it. So evidently
there was some issue that only shows up on Windows XP with Java 1.6. And like, if you
had a Mac you didn’t see it, if you had Vista, presumably, you didn’t see it, if you had
Java 1.5 you didn’t see it. But in that one case, it would come up, so the name suffer web
applet demo was updated a few days ago, I think on Friday, maybe. So now it should
work for everyone, hopefully. If you still have an issue, let me know. The only thing that
you’ll see now, though, if you’ll try running this applet, is that the interactors, instead of
it being on the south border of the screen are on the north border of the screen. That was
just a little hackler we had to put in there to get things to work. The functionality is
exactly the same.
As a matter of fact, if you want, you can put your interactor and border on the north
instead of the south. It’ll make no difference to the rest of your program other than where
you say south for adding your interactors, you say north, that’s the only place it makes a
difference. But you actually see that in the web applet version, the interactors are just in
the north border instead of the south. Otherwise, it doesn’t make any difference. But in
case you saw that and was like freaked out, there’s nothing to worry about. Okay. So
also, I hope you had a good break. Just wondering, how many of you actually enjoyed
their week break? Good time. And how many were working most of that break? Yeah.
Good times. Hopefully, it didn’t cause you too much pain, but if it did, hopefully, you’re
like, all caught up or ahead of the game in all your classes, now, so life is good.
So I want to spend a little bit more time talking about today, well, actually a lot of time
talking about today, is thinking about data structures, building large-scale data structures.
And we begin to talk about it just a little bit before the break and it’s been a while so
we’re going to review it a little bit and kind of build up even more. But one of the things
we talked about, in the past, right, what a lot of our computers do is they manage data.
They manage lots of data. And in fact, I would venture to guess that there’s a whole
bunch of applications out there that manage a whole bunch of data about you, but you
may not have thought about all the data they actually manage. So some of the things that
actually come up, for example, online stores, right. Anyone actually bought anything
online, just wondering. Yeah.
There’s a huge amount of data’s that involved with that. Not only the particular
transactions you make when you buy something, but keeping track of accurate
transactions, figuring out things like people who buy product X also, tend to by produce
Y. All of that is data management. And what makes those companies successful is they
just do a very good job of managing their data. Okay. There are other things like, I’m
almost frightened to ask, but social networks, like, Facebook, or MySpace, or ORCHID,
or Friendster, or Linkdin, or you could just keep going on. Anyone on a social network?
Just wondering. Yeah. That’s good because your next assignment is going to be to
implement one so you can see what it’s actually like. But that will be coming in a couple
of days. And they’re not that hard, really. But what it is is a data management problem.
Right? And it keeps track of things like who you are and information in your profile in
the social network, and who your friends are, and all that happy news.
Or you know, even things like a friend web search, right? There’s a huge amount of data
you need to be able to keep track of to be able to web search, right? So all these things
are all about managing data well and so part of this class, right, is you’ve got a whole
bunch experience in terms of building up code, and different kinds of classes, and doing
nice things with user interfaces, and the whole deal. And one of the things that we need to
spend a little bit more time on is talking about how do you manage lots of data and then
do something interesting with that. Okay. So here’s some principles to think about, if we
think about good software engineering, some of the principles of thinking about data kind
of in the large. Okay.
When you think about keeping track of lots of data, one of the things you want to think
about is the information you want to keep track of, what are the nouns you want to keep
track. And you’re like, I don’t want any nouns, what do you mean by the nouns? Let’s
say I was writing an application that was an online store, to keep track of, oh, let’s say,
music. And so one of the things I would want to think about is, where are the nouns that
are associated with music? You’re like, okay, now you’re really getting weird. No, it’s
pretty simple. Things like a song, right, is a noun, that’s associated with music, or an
album, or an artist, right. And so what you want to think about is the things that are the
nouns in the domain that you’re dealing with oftentimes end up translating into what your
classes are. So you may end up having a class that keeps track of information about a
particular song or class that keeps track of information about a particular album.
So the good linguists out there tell me we not only nouns but we also have verbs, not
unless you happen to be talking to my son, who seems to only have nouns, but that’s a
different story. And he loves jarens by the way. But like, why are you telling me this?
Just cause it’s fun, because I just spent a whole week dealing with it. In terms of verbs,
these are oftentimes the methods that are associated with your classes, right. So when you
want to do something, some noun takes some action, which is a verb, which is some
class, has some method that operates on that class. So at an abstract level that’s what you
want to think about in terms of high-level principles of design. Now, there are some other
sort of more concrete things that you might want to think about, things that have to do
with what are the characteristics of the data you actually want to store so one thing that
comes up, oftentimes, is thinking of the notion of having a unique identifier, identifier.
What do I mean by unique identifier? All of you have unique identifiers, whether or not
you like it or not, as a result of being at Stanford. Your Stanford University I.D. number
is a unique identifier for you at Stanford. Every student has an I.D. number. Okay. So it
identifies you and it’s unique. No two students share the same I.D. number.
So you get issued this number when you show up here and you have it for life. When you
leave it’s still with you. I know, I left, I came back, I have the same student I.D. number.
It just exists and this uniquely identifies you. And in different cases you might want to
think about what are unique identifiers. Right. So in some cases, for example, if you had
a social network you might consider the names of people and not the social network to be
identifiers, or say the names of their profiles, for example. In other cases, you might have
something different. If you’re managing a store you might have some I.D. number for
books, an ISBN number, or if you’re keeping track of music, you might say that the
combination of the songs’ name and the band that plays it is a unique identifier for that
song. In some cases the unique identifier can be a combination of things. But if you think
about your data having a unique identifier that also gives you some insights about what
kind of data structures you might want to use to keep track of certain things. On other
unique identifier that some of you’ve already grapple with is saying Name Surfer. Right?
If you think about the data in Name Surfer what’s the unique identifier there?
Student: Name.
Instructor (Mehran Sahami): Name, right? Name is a unique identifier and for every
name you have some list of values associated with it, which was the rank of that name
over the last century in terms of how popular it was for names. But every name, well, I
shouldn’t say every name has some value associated with it, but every unique identifier in
the system has some value associated with it and only one set of values. And so the
important thing to keep track of there is when you actually are doing your Name Surfer
assignment to fact of this thing is a unique identifier can potentially help you keep track
of the data that you’re using. And we’ll sort of go into that as we go along in the class.
Okay?
So some other principles we can kind of think about in terms of designing data structure,
in terms of actually doing the design, there’s some questions you want to ask yourself.
And the questions you want to ask yourself is, are you keeping track of some collection
of objects? Right? So there comes some collection of objects through data that you want
to have. And if you have a collection of objects, say in an online music store, you might
have a collection of songs that you want to keep track of, this word should be a tip off
too, that perhaps there’s an interesting collection that exist in Java that would be a way of
keeping track of that information. It may not be in Java if you’re programming in some
other language. But the fact that Java has something called a collection and the reason
why they gave the name of collections to a certain group of stuff is because they’re used
to keep track of a collection of objects. And the question that you ask yourself then is
what collections do you actually want to use? Okay.
So with that said, what we can do is spend a moment, and it will be a brief moment,
revisiting the collection hierarchy. Right? You’ve seen this picture before but I’m just
showing it to you again, because the last time you saw it was like two weeks ago, which
is a lifetime in a quarter. Right? I think it too, it’s about a fifth of the quarter. You’re like,
oh, what was I doing two weeks ago? Was the break out, was I learning Printland? No, no
it wasn’t that long ago. But what you were learning about, a little bit, was collections.
And o there are some collections, for example, like an ArrayList that going all the way up
the chain of the hierarchy is itself a collection. Or there are other things, for example, like
a HashMap. And a HashMap, if you said hey, I have some HashMap, the set of keys in
that HashMap ends up actually being a set, which happens to be a collection. Okay. And
so what you want to think about, do I have different things that I can keep track of? Like
an ArrayList is one way to keep track of things. A HashMap may be another way of
keeping track of things. When is the appropriate time to use one thing versus another?
And so when you want to think about the appropriate times of one versus the other, you
want to think about what are the methods that a collection provides to you. And it turns
out all collections that implement the collection interface, like the ArrayList or the key
set of the HashMap, have all of these properties.
And some of you have seen them before, but just to review. You can add a value, right?
So this is a parameterized values type. Like you can have an ArrayList of strings and you
can add some value to it, and it adds it to the collection, and little did you know, or
maybe you did know, but at the time we didn’t’ really care about it, was it returned a
bullion. Most of the times we just returned the bullion, we didn’t care about it. But
actually returned true the collection changed. So in an ArrayList, it always returned true
because when you were adding a value, it didn’t care about duplicates, it would always
just add them to the end and always return true. Some collections, like sets, actually don’t
allow you to have duplicates. So if you try to add something to a set that already has the
value you’re trying to add, it will not change the set and return false, because it says, hey,
I already have that value and nothing changed.
A couple other things that you should know about, most of these you’ve seen. Remove,
removes the first instance of an element as it appears and returns true if a match is found
or returns false if it didn’t find anything to actually remove. And clear, basically, just sort
of nukes the whole collection. It just says get rid of everything in the collection. I’m done
with that and the collection is dead. Actually, the collection is not dead to you, it still
exists, it’s just an empty shell of what it was before. There are violins playing in the
background. And then size, you can get the size of the collection. You’ve seen this,
you’ve probably used a lot of these before in your programs. Contains, that’s an
important one, right? You actually want to see if a collection contains some particular
value, if a collection is empty. And here’s one that’s sort of interesting that we talked
about a little bit but we didn’t actually talk about the fact that a collection or all
collections can give you one these. All collections can give you an iterator.
So we talked about, for example, having an iterator over the key set of HashMap. That’s
one thing we did before. We said we had some HashMap that lets a map from strings
from some other strings. And we want, say, hey what I want to see is get a set of all the
keys and I want to iterate all over those keys. That’s great! You can do that and that’s
perfectly fine. When we used ArrayList we always had like a four loop and said, oh, from
zero up to the size of the ArrayList do something. But if we actually wanted to, we could
have an iterator over the ArrayList and then this would give us the elements of that
ArrayList one at a time. So because an ArrayList is a collection it can also give us an
iterator. And that’s just something to keep in mind is that there’s common patterns that
get used in programming. One of the common patterns that get used is known as an
iteration pattern, which again, is an iterator over some collection and you just go through
and do something like printout the values for every element of that collection. And if you
want to write it in the most general case, you don’t care if that collection happens to be
the key set of the HashMap, or an ArrayList, or whatever, you just say, hey, you’re a
collection, give me an iterator and I can go through all your elements one at a time and,
for example, print them out. Okay. So there’s just simple pattern’s that we get into.
Now, you’re like, okay, Marilyn, that’s fine, you told me some design principles over
here, you told me about some collections over here. Show me something concrete, like
put it all together. So let’s actually put it all together. Okay. And we’ll view a little
example, which is going to an online music store. And because many names for online
music stores are already taken, our music store is going to be called Flytunes cause
they’re tunes that will fly. All right. Yeah, man, when you’re like in your mid 30’s you
just can’t be that cool. But trust me, it is. Okay? So we’re going to make a little store that
just keeps track of music and albums, and that music and actually lets us keep track of
information and prices. And so what we want to think about is what are the things that we
actually are going to do in that store, okay? So one of the nouns of that store is going to
be a song, okay? So a song is some basic thing that we’re going to sell. This is what we
want to be able to do with the song. Now, you could say, well, what does that mean, do I
have some method called sell? If we’re doing inventory management we might not
actually have a method called selling a song, but we might, for example, want to add for
inventory to do things like add songs.
