This presentation is delivered by the Stanford Center for Professional
Development.
Let us
refresh about where we were at the end of Wednesday.
As we had talked about the vector form of the buffer, so the editor buffer that's
backing the
word processing client,
and the two stack version, where we're shuffling stuff, often on the before
and after stacks to get things done, right?
And when we were looking at the main six operations, we're looking at the four
cursor movements and the two editing operations, right, that we had traded off.
Where editing had been slow in the vector,
to where editing was now fast, but then these long distance movements were slow,
because of the shuffling.
And then there was a little discussion at the very end about how this probably
increases our space requirements, because we're now keeping two stacks that are
each capable of holding
the entire contents
as opposed to one vector here
with its slop.
So that was where we were at.
We are still in kind of the pursuit of this Holy Grail of could we
get it to where everything is fast. Is it always a matter of tradeoffs or could we just
invest some more smarts and more
cleverness
and hard work and squeeze it down to where we could get everything to perform
efficiently? So typically when computer scientists say they want something to perform
efficiently, they're hoping for log
in time or faster. Constant time is the best. Log in grows so slowly that in fact,
logarithm time is effectively constant
for all reasonable values of N up to millions and billions.
And so typically anything that is linear or higher is often a weak spot that you are
trying to look at, and certainly things that are quadratic or exponential
are definite opportunities for improvement.
So let's look at this idea of the link list,
so that both
the
vector and the stack
- we're relying on this idea that continuous memory is the
weak link that was causing some problems. In the vector, that shuffling to
move things up and down,
or in the case of the stack version, one side to the other
was part of what we were working up against.
And the link list promises to give us this opportunity to have these each
individual character being managed separately,
and flexibility might help resolve some of our problems here.
SO what we're going to look at is the idea of implementing the buffer using a link
list. So if I have
characters A, B, C, D, E,
I could have a link list here where I'm pointing to the head cell, which is A,
which points to B, and C, and D, and E, and down to the null.
SO what I'm modeling it as in the private data section will be a
little
link list node with a character in there, a pointer to the next one.
And then I'm going to keep two pointers, one to the front-most cell, and then that's going to
model where the cursor is within the buffer.
So rather than doing this like an index, an index was handy in the case of vector where we
had direct access, right?
Given the way the link list works,
knowing that it's at the fifth cell, the fourth cell isn't really very helpful. It would be more
helpful to have the pointer kind of directly in the midst of things to give us direct
access to where the cursor is.
But let's think a little bit about that cursor,
because there's an important decision to be made early about helping to
facilitate the later work we have to do.
I have the contents A, B, C, D, E,
so the cursor is actually between two characters.
If the cursor right now is situated
after the A and before the B,
what I'm
modeling is A cursor B,
C, D,
then
it seems like the obvious two choices for where the cursor might point is to
A or to B. And I
had said in the case of the vector that if it were index zero or index one
that
there wasn't a really strong preference for one over the other.
There is going to be a really good reason to pick one for the link list
over the other. Would you rather point to the A
for where the cursor is or would you rather point to the B? [Inaudible]
Exactly, so the idea is that when the cursor position is there, the next edit
actually goes in between the A and the B. So if I insert the character
Z, it really does go right here.
And if I am going to, if effect, wire that in and splice it in then list,
if I'm pointing to B then I'm kind of hosed, because I'm already one past where I need to be able slice in. Because I need to
know what was behind it to bring it in. So I'm pointing to the character behind the
cursor
gives you access to
wiring this down to here and this into there, and then updating the cursor to
point to the Z
without having to do any of the difficult backward looking backward
traversal.
So that strongly suggests what it is, it's going to point to
A when it's between A and B; B when it's between B and C; and so on.
There is another little point here, which is there are actually five letters
in the cursor, but there are six cursor positions. It could be at the very
beginning,
in between all these, or at the very end.
And the way we've chosen it right now, I can identify all of the five
positions
that have at least one character to the left, so being -
pointing to the A means it's
after A; pointing to the B it's after B; and so on, all the way down to the E.
But I don't have a cursor position for
representing when the cursor is at the very beginning of the buffer.
So
one strategy I could use, right, is to say I'll just use the special cursor
position of null. But
I need one more pointer value to hold onto,
and I could make a special case out of this because there's null. Once I've done that though,
I've actually committed myself to this thing that's going to require all of my code to be managing a
special case of,
well when the cursor's null do something a little different than when
the cursor is pointing to some cell. I'm going to
show you a way that we can kind of
avoid the need for making a special case out of it,
by
wasting a little memory and reorganizing our list
to allow for there to be a sixth cell,
and extra cell that we call the dummy cell.
So in this case that cell would go at the very front.
It would have no character, just let the character field be unstatused. It's
not really a character. What it is, is just a placeholder.
And when I created the buffer to begin with, even when it's empty, it's always going to have
that cell. I'm going to create that cell in advance, I'm going to have it sitting ready and waiting, and that cell
never gets deleted or moved or changed. In fact, the list always, the head
of this will always point to the same cell from the beginning of this object's lifetime
to the end. So it will never change this at all, and the cells that follow are
the ones that are going to be changing and growing and rearranging in
response to editing commands.
What this is going to buy us is a couple of things. First off, it's going to make it
so there is a sixth cursor position.
So now when the cursor is at the very beginning,
we can set the cursor to point to this dummy cell.
Okay
that's one thing that we solve by doing that.
Another thing that we've solved is actually we have made all the other
cells on the list, the ones that are being edited and manipulated.
We've made them all totally symmetric.
Previously there was always going to be a little bit of a special case about, well if you're
the front of the list, we're seeing that sometimes we're doing inserts on the
stack in queue link list. That
inserting later in the list involves kind of wiring in two pointers; one to command and one
to go out.
But there was a special case that oh, if you're the very first cell of the list, then
your outpointer is the same, but your incoming pointer is resetting the head.
That piece has actually gone away now,
that now every cell in there always has a predecessor. It always has a previous,
right? Something behind it so that actually they will always be
pulling the pointer in and pulling the pointer out
for every cell with character data that's being modified.
And that means some of that extra little handing of oh, if you're the
very first cell,
have gone away.
The very first cell is always this kind of dummy cell and doesn't require us to go
out of our way to do anything special for it.
So this is going to solve a bunch of problems for us, and it's kind of a neat technique. This thing
is used actually
fairly commonly
in situations just managing a link list just to buy yourself some symmetry in the
remaining cells.
So let me look at some code with you, and I'm going to actually draw some pictures as I
go. I'm
not going to write this code in real time, because I think it's actually more important to
see it
acting on things than it is to see me typing out the characters.
But the mechanism, right, in the case of the buffer here
is it's going to have a head point,
which points to the front most cell; and a
cursor,
which points to the character that proceeds the cursor. So if right now the
contents of the buffer
are
the contents A, D, C.
And let's say that right now
the
cursor is pointing to A.
Actually, I need my
dummy cell. Let me move everybody down one, so you just have dummy
cell and my A and my B.
And so the cursor right now is at the very front of the buffer.
This is kind of what it looks like. It has two characters, the A and the B.
I'm going to trace through the process of inserting a new character
into the buffer. It
is that my local variable CP
is going to point to a new cell allocated out in the heap.
Let's say the character I'm going to insert is the Z, so I'll
assign
CH to the character, the slot right there.
And then the next for this
gets to - what the cursor is - kind of following the cursor. So the
cursor is pointing to the cell before it,
and the next field of that cell tells us what follows it;
so if I trace my cursor's
next field, it points to A,
and so I'm going to go ahead and
set up this new cell's next field to also point to A.
So now I've got two different ways to get to the A cell, tracing off the dummy cell or
tracing off this new cell.
And then I
update the cursor's next field to point to CP.
So I just copied right there that CP's next field was pointing to A. I copied it down here
to kind of do the splice out.
Now I'm going to do the splice in,
causing it to no longer point to A,
but instead to
point to my new cell down here, CP.
And then I update the cursor
to point to this new cell. That just means that subsequent inserts, like the
C is kind of behind the cursor after I've made this
edit.
That goes away when that one ends,
and so now the new structure that I have here is
head still points to the dummy cell that never changes.
Dummy cell now points to Z,
Z points to A, Z points to B,
and then the cursor in this case is between the Z and the A,
by virtue of the fact that the cursor is pointing to Z.
A subsequent one would kind of do the same thing. If I typed out ZY
after I did this. We'd
make a new cell over here. It would get what
was currently coming out of the cursor's field. The next field, right, we would
update cursor's next field to point
to this new one. And then we would update cursor
to point to this guy. And
so now following the list, right, dummy cell,
Z,
Y, A, B, cursor pointing to the Y, which is the
character directly to the left of the cursor.
And so inserting in any position now,
front cell, middle cell, end cell,
doesn't require any special case handling. So you don't see any if of things.
And you notice that you'll never see an update to the head directly here.
That the head was set up to point to the dummy cell in the constructor
and never needs any adjusting.
It's only the cells after it that requires
the new
arrangement of the pointers coming in and
out. When I'm ready to delete a cell,
then the mechanism for delete in the buffer is to delete the thing that follows
the cursor. So if I have Z, Y, A, B,
this is the character that delete is supposed to delete, the one after the
cursor.
And so,
the first thing it looks at is to make sure that we're not already at the end.
In the case of the link list form of this, if the cursor was pointing to
the last most cell,
and then we looked at it's next field and saw that it was null, that would be a clue. Oh, it's
pointing to the very last cell, there's nothing that follows it. So we have a
quick test to make sure that there's something there to delete.
There is something following the cursor, and
in this case since the cursor is pointing to the Y, we're good. It says look at its
next field, it points to A.
It says okay,
call this thing old
and point to that A.
Now do a wire around it.
So take the cursor's
next field, and
so this thing is where I'm targeting my overwrite,
and copy out of the old its next. It's
no longer pointing to the A, but instead it's
pointing to the B.
And deleting the old, which
causes this piece of memory to
be reclaimed,
and now the contents of my buffer have been shifted over to
where it goes Z, Y, and straight to D. The cursor in this case doesn't move. It
actually deleted to the right, and so
whatever was to the left of the cursor just stays in place.
So again, no need to update anything special for the first or the last or any of those
cells,
but the symmetry of all the cells past the dummy kind of buys us some convenience
of handling it. What does a dummy cell look like? The
dummy cell looks like just any other cell. It's actually a cell, T, and what you do is
you just don't assign the Christian field, the character field, because it has nothing in it.
So it actually looks just like all the others, it's just another node in the
chain.
But this one, you know you put there purposefully just as the placeholder.
So it doesn't contain any character data. So if you're ready to print the
contents of the buffer, you have to remember the dummy cell is there,
and just skip over it. You
tend to start your list
at heads next, the first interesting cell to look at, then work
your way down to the end. So it's
just like all the others, but you just know
that the character data here is useless, it's not important. You didn't even write anything in there. When you delete, you just go left? It turns out
the delete in this
case goes forward.
So you can imagine that in some other world it does, but all the ones we
have done so far have always deleted forward. So the delete - for example, the stack case,
grabbed from the after stack
- it's done that way, because it happens to simplify some other
things that you can imagine that delete and reverse. What would it take? Well, you'd have to back
the cursor up. And we're going to find out pretty soon that would make it
challenging for the link list. So partly we've picked a delete that
made certain things work out a
little better for us.
So both of these operations
are O of
1;
this is where the link list really shines, right, on this sort of stuff. Because
if you have access to the point at which you want to make a modification, so if you are already kind of
in the midst of the thing you're trying to rearrange,
it's often to the link list's advantage, because it actually can do these this rewiring
in the local context. And even if there's thousands of characters that
follow the cursor.
It doesn't matter. And there can be thousands of characters preceding the cursor
for that matter, too.
The idea that there's a much larger context that's working and doesn't impact
its performance; it's really just doing this local little rearrangement of the pointers.
And that's a real strength of the link list design
is that flexibility that doesn't rely on everything living in contiguous memory.
So let's talk about the movement options for this guy.
So right now I have the contents
Z, Y with
the cursor
between that, and the B following that. So three characters worth,
and then
the
initial two operations
are pretty simple. The later two are going to be a little bit messier. So let's look at
the easy ones first.
Moving the cursor to the beginning, so that jump that pulls you back to the very
beginning,
very easy in a link list form. If I want to move the cursor to the beginning, all
I need to do is take that cursor pointer,
and reset it
to the head, which is where the dummy cell is. And so, by
virtue of doing that,
the character it points to is the one that's to the left,
right of that, and to the left of that the dummy cell is one we're not
counting. In fact, it's like nothingness that's there,
and that means that the first character that follows the cursor is Z, which
is the initial character of the buffer. So that reset, easy to do, we have
easy access to the front of the list,
and so
no
special
crazy code required.
Moving the cursor forward, also an easy thing to do, link
list are designed to make it easy to work your way from the front to
the back. And so moving the cursor forward is advancing that cursor by one step. So
in the array form of this, what was a cursor plus, plus, the
comparable form of that in the link list is cursor equals cursor next.
It has a little
if test there, all of the versions actually have something that is
comparable to this. If you're already at the end, then there's
nothing to be done, so you don't advance the cursor off into space.
You
check to make sure that there is something for it to point to. So in this case,
seeing if the cursor's next field is null, it's not, it points to Z. Then we go
ahead and update the cursor to there,
which has the effect of
changing things to where the Z is the character
to the left of the cursor, and then the YB follows it.
So moving this way, getting back to the beginning, and kind of walking our way down is kind of easy
to do.
Now we start to see where the link list causes us a little bit of grief,
moving the cursor to the end.
So now, starting at the beginning or the middle, or wherever I am,
I want to advance my way to the end. I don't know where the end is.
Link lists in general don't keep track of that,
that in the simple form of the single link list, I'm going to have to work to
find it. So I'm going to take where I am and walk my way down.
And this one actually just makes use of an existing
public number function to move cursor forward. It's like while the cursor next does
not equal null, which is to say while we are not pointing at the very last cell of the link list,
then keep going.
So advance cursor equals cursor.
Some will say,
"Is the cursor's next field null?" No, then set the cursor to be the cursor's
next field.
Is the cursor's next field null?
No it's not, so advance the cursor to the next field.
Is the cursor's next field null? Yes.
So that would
the last thing in the buffer,
and so if we have
hundreds or thousands or
tens of characters, whichever it is, right,
and depending on how close we already were, it will walk through
everything from where the current editing position was to find the end of the
buffer
one by one, working it's way down.
Even more painful
operation
is the simple one of just moving backwards.
If I'm pointing right now to that B,
and I'd like to get back to that Y, the
link list is oblivious about how you got there. It knows where to go from
here, but that backing up is not supported in the simple form.
In order to find out what preceded the V,
our only option right now is to go back to the beginning,
and find it.
So starting this pointer CP at the head,
and saying,
do you point to;
is your next field the cursor?
And this one says, no. And then it says, well okay advance. Does your next field point to
the cursor? No it's not. Go to this one, does your next field point to the same place
as the cursor, yes. Wise next field, points to the same place the cursor
does.
That must mean that Y was the one that preceded the cursor in the link
list. So after having gone back to the beginning and walked all the way down, especially if I'm near
the end, that's a long traversal.
And when I get there, I can say "Oh yeah
that's the one, back it up to there."
Walking it all the way down;
some good link list coding, good practice in there, but
again a funny,
funny set of trade offs, right?
Does anybody have any questions about any part of the code?
At the end
could you just
save the address of the pointer, and then the
person
who wants to go to the end could just
access that? That was a great idea. It's like, so what about
improving this? Right now all we have is a pointer to the front, and each
pointer has only a pointer to the next. It's like, maybe we need to add some
more stuff, track
some more things. What if we tracked the
tail? Would that help us?
If we tracked the tail, we could move to the end quickly. Would
that help us moving backwards?
No. It solves one of our problems though, so you're on to something.
Let's look at what we've got, and then we'll start thinking about ways to fix it, because that's going to be
one of the pieces we're going to think about.
So if I move to link list
relative to what I have,
again, it's like a shell game. The old ends moved.
It used to be that editing was slow and we didn't like that.
Then we made big movement fast,
and now we have this funny thing were moving in certain ways is easy and
moving other ways is bad. So moving
down the document
is good, moving backwards in the document not good.
Moving back to the beginning is good, but moving to the end is bad.
But then editing in all situations is good,
another sort of quirky set of things. It just fells like it's like that game where the
gophers pop there heads up, and you pound on them. And they just show up somewhere else. As
soon as you get one thing fixed, it seems like something else had
to give.
This, I think, would actually be my ideal editor, because it turns out I
have exactly this working style, which is like, I'll be down at the end of
the document, and I'll have to be generating new things. And
I'm getting tired and I don't like writing, and what I keep wanting to
do is I go back to the beginning. And I read that again, because I worked on that the most and
it's nice. And so I go back to the beginning, and I'm like oh yeah, look at this. Look at how lovely this
is,
and then I never want to go back to the end where all the trouble is. So I just
keep going back to the beginning and editing in the front, and then slowly get
back to the end. And then I don't like it again, and then I go back to the beginning.
But I never actually willingly go to the end
to face my fears. So
this is the editor I need.
Also
has a bit of kicker in terms of space.
So if the space for a character is 1 byte, which it typically is,
and the space for a pointer is 4 bytes, then
each of those link list cells is costing us 5 bytes, right?
Which is
sort of five times the amount of storage that the character itself
would have taken alone,
so in the vector it's fairly tight, a little bit more going up on that. But we've actually kind of blown
it up by another factor of two even beyond the stack, which is not quite a
good direction to be going.
So let's talk about what we can do to fix that.
I'm not going to go through the process of this. I'm just going to kind of give you a thought
exercise, so you can just kind of
visualize it.
What we have here, right, is an information problem. We
only are keeping track of certain
pathways through that link list.
What if we actually increased our access to the list?
We don't need to have the full access of a vector, being able to know the nth
character by number is not actually as far as we need to go. But we
do just need a little bit more coordination between a cell and its neighbors.
So the two things that would buy us out of a lot of the things that we're seeing
here is if we added a tail pointer.
So if I just add a tail pointer that points to the last cell, then I can move to the end
quickly.
You say cursor equals tail; the same that cursor equals head. So what was an O of N
problem now is an O of 1.
The backing up,
not as easily solved by just having one thing that's going on;
I also am going to need,
on a per cell basis this ability to move backwards.
Well, it's just symmetry, right? If A knows where B is, and B knows where C is, and C knows where D is, what's to stop
it from also just tracking the information going in the other way,
so that D knows that it came from C, and C knows it came from B, and so on.
And so having this completely symmetric parallel set of links that just run the other
direction,
then buys you the ability to move backwards with ease.
The other thing that this would give you is the tail pointer
is almost not quite enough to give you the exact place of the end. It gives it to
you, but you also have to be
careful about what is it going to take to update it?
And so inserting can easily update the tail pointer. It's the deleting that kind of
would get you into trouble. If you were
here and deleting, you would have to kind of keep track of making sure if you were deleting
the thing that was the tail pointer, so you have to be a little about making sure
you don't lose track of your tail.
But once I have both of these in place,
I suddenly have something that can move
forward easily, O of 1;
move to the front easily, O of 1; move to the tail easily, O of 1; move backwards O of 1.
So I can make all of my operations
O of 1.
Deleting, you're still going to have to delete the individual cells, but there's one place where
it suffers, but that's a much more rare occurrence.
And I can get all six; it moves fast, in every dimension;
inserts and deletes
all good.
And there are two places we paid for it.
One is certainly the memory.
So a 4 byte pointer one direction, a 4 byte pointer another direction,
plus the 1 byte for the character means we have a 9 byte per
character
storage usage.
And the other way, which is a little bit hard to represent with some number
in a quantitative way, but actually it's also an important factor, which is
your code got a lot more complicated.
If you looked at the code for the vector of the stack version, it was a few
lines here a few lines there.
If you looked at the code for the link list singly we looked at, it's like you've got
to wire up these pointers.
Now imagine you've got to wire up twice as many pointers.
Not only do you have the in and out going one direction, you'll have the in and out going the
other direction,
and just the
opportunity to make errors with pointers has now gone up by a factor of two.
The idea that you could get a vector version of this up and running in
no time,
compared to several days, let's say, of getting the doubly link one working. It
might be a factor to keep in mind.
If you're kind of investing for the long haul, sure, work hard, but know
that it wasn't for free.
So you've
got 89 percent overhead.
That's a lot of overhead for small bits of data.
More likely, and this is actually the way that most modern word processors
do do this,
is they don't just make one or the other; it's not just a array or a stack or a link list.
They
actually look at ways to combine the features of both to get a hybrid,
where you can take
some of the advantages of one pipe of data, but also try to avoid its worst
weaknesses. So the most common way they're going to do this is some kind of
chunking strategy,
where you have a segment of the
buffer that kind of is moved aside and worked on in one little array. It
might be that those arrays are ten or 20 or a sentence long, or paragraph long.
It might be that they are actually dictated by when you change styles.
All of the code that's in one font
kind of gets moved into one chunk, and as soon as you change styles, it breaks
into a new chunk that follows to kind of keep track of the formatting information. It
depends on some of the other features that are present in the processor
here, but it's likely that rather than having all 1,000 or all 10 million
characters in one
data structure,
they're actually kind of separated
to where you have a little bit of both. So the most likely thing is that
there is some kind of array strategy on a chunk basis.
There's a linking between those chunks.
And what this allows you do is to
share that overhead cost.
So in this case, if I had every sentence in a chunk by itself,
and then if I had next and previous pointer, which pointed to the next sentence and the previous
sentence, when I need to move the cursor forward or backwards
within a chunk, it's just in changing this index. Oh, it's in index two, but
now it's moving to three, or four, or five.
And then when it gets to the end of that chunk, to the end of that sentence, and you move forward, well then it
follows the next link forward.
Similarly moving backwards, right, so
within a chunk doing array-like manipulations, and then as it crosses the
boundary using a link list steps to get further down.
So when it needs to move to the front or the back, those things are easily
accessible using head and tail pointers.
When I need to do an edit,
it operates in this array-like kind of
way
when there's space within that chunk. So you start editing in a sentence, then it
would kind of do some shifting on that array. But the array itself being pretty
small
means that although you are paying that cost of shuffling,
you are doing it on a smaller chunk. It's not 1,000 characters that have to move, it's
20 or 40 that have to move within that sentence.
And that when
you need to insert a new sentence or a new chunk in the middle, you are doing
link list-like manipulations to build a new chunk and insert and splice,
so you have that flexibility, where the many characters aren't
all affected by it. So you have kind of local array editing
and global link list editing
that gives you kind of the best of both worlds.
But again, the factor is cost showing up in code complexity.
That what you are looking at is kind of space/time tradeoff. Well, I can throw space at
this, and most people will say that in computer science, "Well I can throw space and this and
get better times." So
the double link list is a good example of something that throws space at a problem to get better
time. There's a lot of overhead.
Moving to the chunk list says I want to get back some of that space. I'm
not willing to invest 90 percent overhead to get this. Can I find a way to
take a
whole sentence worth of things and add a few pointers here? That means that
there's only two
4 byte pointers per each sentence as opposed to each character,
and that really way reduces the overhead.
But then now,
the problem is still back on your shoulders in terms of effort,
now I have both an array, and a link list, and double links, and
a
lot of complicated stuff flying around to make it work.
But it does work out.
It's kind of the process that designers go through when
they're building these kinds of
key structures. It like, what are the options, and do any of the basic
things we know about work? What about
building even fancier things that kind of take the best of both world and mix
them together and have a little bit of the weaknesses of this a little of that, but none of
the really awful
worst cases
present in the end result.
So in this case you'd have a lot of things that were constant time where constant was
defined by the chunk size.
So O of 100, let's say, if that was the maximum chunk size
to do these things, as opposed to O of
N for the whole block net,
so kind of a neat
little thing to think through.
There was a time, just so you can feel
gratified about how I've worked you very hard, but actually in the past I've been
even harsher.
We actually had them build the doubly linked chunked list editor buffer,
and now we have you build the singly linked chunk list PQ, and it's
actually
still very complicated, as you'll find out, but not nearly quite as hairy as the
full in both directions every way
craziness.
And you can kind of imagine in your mind.
Any questions about edited buffer?
We?ve got two more data structures to implement,
two more things that we've been using,
and happy to have in our arsenal that we need to know how they work.
Let's talk about map first, and in
fact the strategy that I'm going to end up showing you for map is actually going to be
the same one we use for set, then we'll come back and think of an even more clever
way to do map, too. So
we've got two things to talk about, which are binary search trees and hashing. We'll
do binary search trees first,
and then we'll get back to the hashing the second time around.
So
map is, next to vector, probably the most useful thing you've got going on in
your class library,
all kinds of things that do look up based
activities; looking up students by ID number,
phone numbers,
by name, any of these kinds of things where you need to have this key at associated satellite
information. And
you'd like to be able to do that retrieval and update quickly.
The map is the one for you.
So if you remember it's key value fears, it's all about key being the
identifying mark that allows you to find the associated value. And then the value
is actually just being stored and kind of retrieved without using it
or examining it in any kind of interesting way.
And what we're really interested in here is how to make this guy work really efficiently. So efficiently
being hopefully log in or better,
if we could get that on both the update operations that add and remove things
from the map, as well as the
look up operation, then
that would please probably all our clients immensely, if we could get both of
those going well.
So I'm going to build you on that. I probably have enough time to do that.
That
attacks it from
using simple tools to start with, just to kind of get a base line for what we can do.
Vector, our old friend vector,
can't get too much mileage out of vector, apparently, because you can always find a
way to make it do something
useful for you.
It
gives us the convenience
of managing that thing with low overhead,
direct access is good.
We make a parastruct
that has the key and the value together.
We store it into a vector,
and then we
may or may not sort that vector. But if it's sorted, there's probably some good reasons. Think
about
what order to sort it in, what information to be using to sort that,
and then we'll get value to add. We're just going to go
through doing it, rather than talk about it.
We'll just go over and
make a vector happen.
Let's get over here in X-code.
Let's take a look at
my map dot H,
and all
I'm going to put in there is actually add and get value.
And
the other one contains key and remove."
But these are these two operations that really matter to us, getting something in there, and
getting something back out.
And so I'm going to start by
building this thing on vector. So let me go ahead and
indicate that I plan to use vector as part of
what I'm doing. So I defined a little structure
that's the pair. I'm going to call that "pair"
even, that's a nice word for it. So the pair of the key and the value that go together,
and then what I will store here
is a vector of those pairs. They'll
give me a key to value; I'll stick them together in that little struct, stick them into my vector, and
hopefully be able to retrieve them later.
So given that I'm depending only on vector, I don?t have any other
information, I don't technically need to go out of my way to disallow then
memory-wise copying, because vector does a deep copy. But I'm going to leave it in there, because I
plan on going some place that is eventually going to need it. I might as well be safe from
the get go.
The vector
will be set up and destroyed automatically as part of management of my
data member. So I actually don't have any explicit allocation/deallocation, so if I look at my
constructor and destructor they'll be totally empty.
And then add and get value are where I'm going to actually get to do some work.
Before I implement them, I'm just going to think for a second about
how this is going to play out.
Let's say I'm doing a vector that's storing
strings and their length. Let's say, it's just a map of
string,
and if I do M dot add
car. I'm going to store a three with it,
so on the other side of the wall,
what we're going to do is make a little struct
that has the word car
and the number three with it, and we package it into our ray.
And so then we get a second call to put something in like
dog, also with a three, then we'll make a second one of these and stick it in
our ray.
And so on, so the idea is to have the vector really kind of manage where the storage is going. And
then what
we'll just do is package it up and stick it in there.
The one thing, though, that I have to think a little bit about, because it sounds
like add should be pretty easy. It almost seems like what I need to do is something
as simple as this. And
I'll start to write the code, and then you can tell me why
this isn't what I want to do.
I say pair TP, and I say P dot
key equals key P dot
value equals val, and then I say entries dot add P.
Almost, but not quite what I want,
what have I forgotten
to take care of?
If it's not already in there;
this has to do with just what's the interface for nap. What does nap say about it if you
try to add
for a key a different value. So in the case of this one, it didn't quite make sense that I would add
something, but let's say I accidentally put car in there with a link to the first time that I went
to go fix it, right,
that my subsequent to ask it store car with the proper value,
three,
doesn't create a totally new entry.
It has to find the existing entry that already has car and overwrite it.
So the behavior of mad was it could add when it was not previously existing.
It also could be an overwrite of an existing value. So we do need
to find
if there is an entry that already has that key, and just
replace its value
rather than
add a second entry with the same key. So at any given point, right, in this whole
vector, there should be one entry
for each unique key.
So I have to do a search. And
let me
write this code, and then I'm going to mention why I'm going to decompose it in a
second.
If I do entries dot size, I plus plus
then if
entries of I dot key equals key.
Then
let's break. Let me pull out
I so I can get access to it when I'm done. So after this
loop exits,
if I is less than entries dot size,
then
I know that it found a match.
In the case where it went through all of them, and it never hit the break. Then I will
have gone all the way to where it is exactly equal to entries dot size; if it didn't then I
just
have a place to overwrite. And I can say entries of
I dot val
equals val.
Otherwise I go through this process of adding a new one. I had to
go hunt that thing down
and replace it.
That code,
when you look at it, you can say, "Gosh I feel like that code's going to be familiar."
Because that idea of searching to find a match to the key
probably is going to come in really handy
when I need to do get value,
but it has the same exact problem of oh, I've got to go find that match. So in fact,
that kind of motivates the idea of why don't I just take this little piece of code
and separate it out and do a helper that they can both use. I
may not have planned for this from the beginning, but once I see it happening, I might as well fix
it. So I can say find index
for key that
given a key will return to you
the vector index at which
that key is or a negative one. I don't know if I need to keep that
one anymore.
If it ever found it, it returns I otherwise
it returned negative one. That can be our not found.
I can actually use that up here,
and then I can say, if found
does not equal negative one.
Then we do that,
and then that
tells us that
this little piece of code is going to come in handy right up here,
get value if found does not equal
negative one, then we can return that
and what is the behavior of get value if it didn't find it? Does anybody remember?
I ask it to get the value in this case for lollipop and it's not
there,
does it turn zero, what does it
do? Untracked forget value, remember?
This is an error.
There is not sort of a
general case return value you can produce here
that will really sort of sufficiently describe to someone who's made
this call in error what happened, right? I can't return zero, because it happens to be
that sometimes I?m putting in, and sometimes I'm putting strings or structs
kinds of things. There's no general zero or negative one to use,
so the behavior of get value is if you ask it to retrieve a value for a key, it ought to be
there. So
the corresponding implementation would likely also just go through
the process of contains key, which we call find index for key and check.
It could be used by the client
if they need to know in advance that it's really there.
So let's see how I'm
doing. Let's go back to my
code here,
and this
being
not my specialty,
and just see that I can put something in and
get it back out would be a good first test to see that things are
going as they should. Oh, no it didn't like that. Oh yeah, find
index for key.
Find index for key
was not
populated clear in my dot H, so let me go move it there. I'll put
it in the private section, because I don?t want this to be something that is
exposed outside of the implementation. The idea that there is an index and
there is a vector is not really something that I would want to make part of my
public interface. It's really just an internal detail of how I'm managing stuff.
Something about what I did, oh yeah, I
used the right name for that.
One more case let
me just take a look at them both
before I let the compiler tell me what is and what isn't right about them. Their both
doing find index for key using linear search. If it comes back at not negative one
pulling out the matching value and overriding it, and then in the case of adding
or replacing the error -
so the
previously stored value for that is three,
and if I go and I do one of those tests it's always good to know what
happens if I ask it for something that doesn't exist.
Making sure that the error handling that I put in there does
what it was supposed to do, right? Are
there any questions about the code that I wrote here?
The vector is always kind of a good starting place for these things, because actually it just
tends to use very simple things, and it tends to lend itself to easy code.
But because of vector constraints being at a contiguous back structure, right, there's likely to
be some
performance implication. And in
particular,
in the unsorted case here,
both add and get value
involve doing a linear search.
In some cases it will find it quickly at the very beginning or even half way
through.
In other cases it won't find it at all and have to search through the whole thing. So on
average, if you figure it's equally likely to be in any position or not there at all,
it's at going to at least have to look at half of them or more.
And so we can say they're both linear.
If we change it to be sorted,
which is the first obvious improvement to make here,
then get value
gets a lot faster, because we can take advantage of binary search.
I sort it by key,
so ignoring the value, values are just satellite data. But stored in order of
key,
then all the A words, B words, C words, D words, what not, so
walking it down the middle and seeing which half you look at, then looking at the
quarter of there and the eight of there. It's going to very quickly narrow down on
where it had to be if it was there or if it wasn't there at all.
So we can implement that in logarithmic time, meaning that if you 1,000
entries, it takes ten comparisons to find it or agree that it's not there.
If you double that it will take one more comparison. If
you go to 2,000, negligibly faster, even numbers in the millions
are still just a handful
of comparisons to work it out, and say,
to the twentieth for example is roughly a million; so 20 comparisons in or out,
and so it didn't look at a million things a million times over.
However,
that didn't improve add,
why not?
Why does keeping an assorted order
not have the same boost for add as it did for get value?
Can I do the same logarithmic search? You have to
move all the elements ?
Yeah,
you can find the place fast, right, you can say returning the word
apple it's like oh, okay. I can very quickly narrow in on where it needed to be. If it
was there I could override it quickly, but in the case where it really needed to do
an add,
it's got to move them down.
So the old add
did all its work in the search and then just tacked it on the end if it didn't find
it, or overrode the middle. But the new add
also has to modify the array to put it in the right place, and putting it in the right place means
shuffling to make space.
So even though it found it quickly,
it was unable to update that quickly, so it still ends up being
linear in that case.
Now this actually not a terrible result,
as it stands
it's probably much more likely that you're going to load up the data
structure once and then do a lot
of searches on it, then infrequent additions. That's a pretty common usage
pattern for a map. It's kind of like you
build a dictionary, right,
loading the dictionary once could be expensive, but then people get tons and tons of
look ups of words later. But you don't change the definitions a lot later or add a
lot of new words.
So
this might actually be quite tolerable in many situations
that the building of it was expensive, but it gave
you
fast search access.
But really what you want to do is say, can we get both of those? So driving to say
what we do with the editor buffer, you say, "Well, what if I just want both of those operations
to be logarithmic or better, what can I do?" So
I'll leave you with kind of just
a little bit of a taste of where we're heading.
Just to think a little bit about what the link
list does and doesn't buy us,
right, that the link list gave us flexibility
at the editing, the local editing site, but it doesn't give us fast searching.
Well maybe we can take this link list and try to
add searching
to the idea of this flexibility to kind of get the best of both
worlds. So that's what we're going to start on Monday, building a tree. So if
you have time today, I'd love to have you come to Truman, and otherwise have a good
weekend, and
get your PQ work in.