- Hey, how you doing?
So we're going to continue our discussion
about dynamic equivalence, the dynamic equivalence problem
and the implementation that makes use of disjoint sets.
And we're going to talk about two things, weighted union
and path compression, and those are both ways of speeding up
this implementation that we started in last video.
So let's take a step back real quick
and restate the problem.
The dynamic equivalence problem is that we're working
with a collection of objects and we'd like to do two things.
We'd like to be able to determine
if two objects are related to one another.
That is by some equivalence relation.
So we're asking the question, do they belong
in the same set, which is disjoint from all of the sets.
And we'd like to also be able to connect objects
to join them up by introducing some equivalence.
And we do that. That's essentially by merging sets.
We'd like to be able to do both of those things
as quickly and as efficiently as possible.
And that's the dynamic equivalence problem.
And we saw in the previous video that there's a trade-off.
We tried optimizing for find and we were able
to implement find in constant time at the cost
of making our union operation a linear time operation
which we found unsatisfactory.
And so we started working on optimizing for union
to see if we could get better performance that way.
And we got ourselves into a little bit of a pickle.
So just to recap, we have that find method
that's determining whether or not two elements
are equivalent and the union
which is merging two equivalence classes.
And this is about where we left off with the code.
We have three methods, get root, find and unite.
And again, we tried to optimize for union
but there's a catch.
What's the catch?
Well, we see that both find
and unite make two calls to get root.
So their performance is dependent
on the performance of get root.
If get root is slow
both find and unite are going to be slow.
So the limiting factor here is the time that it takes
to find the root.
And if you'll recall to find the root of any element
we would start at that element
and we would trace steps back to the root
by following pointers to the individual parents.
And if the path is short, that's great.
It performs very well.
But as we saw in the earlier video,
some of these paths can get pretty long.
For example, we saw this structure here
on the right that grew to have a height of four.
There were four edges we have to traverse
from the most distant leaf to the root.
And there aren't that many elements here.
So you can imagine that if we have a large N
and we've performed a large number of unions
that we could get a tree that's pretty tall.
And the longer the path, the longer it takes
to find the root and there's our problem.
So while the union itself, the merging of the sets
takes place in constant time, the union method
has to call get root to figure out
what roots it wants to merge.
So if get root has linear complexity
then that places the limit on union and on find.
So if get root has a linear complexity
we certainly can't do better
than linear complexity with find or union.
That's not possible.
So here we have the situation that linear time
for find, we've got linear time for union.
And that means that we have a worst case
for M operations of big O of N times N
and with M approximating N that's big O of N squared
and N squared, as we've said before, is yucky.
We don't want that. That's too slow.
Particularly when we have a large number
of elements that we want to merge
which is entirely plausible
given the memory capacity of modern computers.
So what do we do?
We've got to speed things up.
Well the obvious thing, shorten the paths to the root,
but how do we do that?
So we're going to see two approaches that are both based
on very simple observations.
The first approach considers why we get long paths
in the first place, why do we have these tall trees?
And it tries to avoid making tall trees.
That makes sense.
You don't want to tall trees, try not to make them.
The second approach considers what we can do
to shorten paths that already exists.
So we have these paths and we have to do this stepping
to find our way back to the root.
Maybe we can do something while we're tracing that path back
to the root, to speed things up by shortening those paths.
And that's called path compression.
We'll see that in the second half of this video.
But first let's start with weighted union.
Again, this has to do with the question
of what makes our trees tall.
Instead of tall trees, we want wide trees,
we want flat trees.
We want balanced trees that don't have these long paths.
So how do we do that?
You recall from the previous video
we had this state where we had five disjoint sets.
We had this set here rooted at one, it has three elements.
We have this set here, that's rooted at seven,
it's got six elements.
And then we have three singletons over here.
Now what happens if we perform a union
say of eight and three?
Well, okay.
We're going to take a look at three
and we're going to see that its parent is one.
We trace that back to one.
We find that one's parent is one, one equals one.
That must be a root. So three's root is one.
One is the representative for that equivalence class.
What about eight?
Well, eight points to zero,
zero points to seven, seven equals seven.
So seven must be the root.
And so seven is the root associated with node eight.
And that's the representative for that equivalence class.
Now, according to the algorithm as we've written it so far,
what we would do next is we would essentially
graft this tree onto this root.
We would make seven a child of one.
We would update the pointer here from seven to one.
It's also joining these two trees.
But if we do that, we get this structure,
which if you may have noticed
we just grew the height of our tree by one.
We went from a tree that was,
well we went from a tree that was of height one
and a tree that was was of height three
to a combined tree of height four.
And that's if we make this node here a child of this root,
but what if we were to do it the other way,
what would happen?
Well, we'd get a structure that looks like this.
Now here, you see this was the other root.
And we changed that pointer to point to seven
and seven becomes the root for the whole thing.
And now we have a tree interestingly,
that still has a height of three.
So in this case, all the elements are correctly
in the same set, but now the height of the tree is three.
Oh, what happened?
Well, in the first instance, we grafted the taller tree
onto the shorter tree and our height grew by one.
In this instance, we've grafted the shorter tree
onto the taller tree and the height is unchanged.
Now we can't go around calculating the height of these trees
every time we want to do another union operation.
Calculating the height of a tree
is kind of a costly operation.
And we don't want to burden things
with that calculation.
So what we want to do is we want to find something
that's quick and easy, not computationally intensive.
It doesn't really add anything to our process
but it allows us to make good guesses
about how we should join these two trees.
What we want is something that's a quick and easy way
to reduce the likelihood of grafting a taller tree
onto a shorter tree.
So can you think of what that might be?
Let's take a step back.
Without calculating the height of each tree,
we could simply keep track of the number of elements
or nodes in each tree and that can be done
with some very simple bookkeeping.
Then when performing union we'd always set
the root of the tree with fewer nodes
to be the root of the tree with more nodes.
So here we have a tree with three nodes.
Here we have a tree with six nodes.
And so that would tell us to attach the smaller tree
to the larger by setting the root of the smaller tree
to point to the root the larger tree.
That gives us this alternative structure
which is shallower. It has a depth of three.
We didn't increase the depth by joining the two trees.
And we have this shorter configuration.
Now, how do we accomplish this in our code?
Well, here's the start of a weighted quick union class.
And you'll notice that it's a little different
than what we've seen before.
We're introducing this new vector here.
I'm calling it sizes. It's also a vector of ints.
We still have the vector of ints called elements
where the ints are the pointers to the parents.
But here we have this new vector called sizes,
which keep track of the sizes, makes sense.
And so when we instantiate an object of this class
we call the constructor.
We pass in the size.
It resizes both vectors to the same size, and then it goes
and it initializes all of the values
in the sizes vector to one.
Now, why do we do that?
We do that because we're starting off
with a collection of singleton sets.
At the beginning every element
is in its own set of size one.
Every element is its own root.
It's just this one root one leaf tree.
And so that's why we initialize all the values to one.
Then we also have to make a change to our unite method.
And the change is pretty simple.
All we have to do is perform a comparison of the sizes
once we find the roots of the two trees.
So we compare the tree rooted at A
and we compare the tree rooted at B and we make a decision,
and all we're deciding is which tree
to graft onto the other.
And so if the tree rooted at A is the smaller,
we'll graph that on B.
And if the tree rooted to B is the smaller one
or if they're equal, we'll graph that onto the other.
And that's very simple.
The only other step here you'll notice
is that we have to increment the size of the tree.
So all we're doing is we're adding the size
of the smaller tree to the preexisting size
of the larger tree.
Notice that we only have to do this once.
There's no need to update anything else
since all that matters is the number
of the elements in the newly combined tree.
So we don't have to go through all of the tree
and update all of the sizes of all of the sub trees.
We just need to keep track of that root.
And you might wonder why that's okay to do that.
Well, we have no method that breaks the trees apart.
We only have a find and we only have a union.
So once two trees are joined,
we're never going to break them apart.
So once a node that was once a root,
and they all started out as roots,
once a node that was once a root is no longer a root
it will never become a root again.
So we can just ignore the value that might be there.
So we only have to make this one addition.
Addition takes place in constant time
and we have a very simple operation here.
Now it's true that we have to initialize the array,
but the cost of that initialization
is amortized over all future operations.
So that becomes trivial and the updating of the sizes
as I said, takes place in constant time.
But what effect does that have on the height of the trees
and the time it takes to find the root?
Well by using this approach
the maximum height of a tree becomes log N.
And so we wind up with performance like this.
If the height of the tree is log N,
then we can't possibly have a find root operation
that takes more than log N steps because all that's doing
is counting, or I shouldn't say counting,
I should say taking those steps
from the child to the parent, up to the root.
And if the tallest tree we can make is of log N size
then we can't take more than log N steps
to get to the root from even the most distant leaf.
So now, now we have find and union operations
that have a complexity of big O of log N,
and that's a big improvement over big O of N.
Log N is sublinear.
And you'll notice that the worst case for M operations
which was approximating a big O of N squared
is now big O of N log N.
And that again is a big improvement.
And this is resulted from a very
very simple operation or observation I should say,
that we were producing these these long paths
and we did this very simple thing.
It's not precise, it's not guaranteed,
but in the main it will give us
wider, fatter, shorter trees.
And that's kind of cool.
So now the next question is, can we do better?
And again, the answer is yes
based on another simple observation.
So let's move on to path compression.
As I said, this technique is called path compression
and let's consider this problem instance.
Again, we have this tree here rooted at one,
the tree rooted at seven and a few singletons.
And let's say we want to perform the operation
find two, three.
Two is here. Three is here.
That's a quick and easy one, three points to one.
One's a root, we're done.
Okay. So let's take a look at this longer path
and see what happens here.
So as we step from node to node until we get to the root,
we're traversing this path and there might be a way
that we can shorten the path or part of the path.
So let's take a look at the little code here.
This is the same get root function that we had before.
Except I've added this one line here.
Elements sub node equals elements sub elements of node.
What is that doing?
Let's think about this for a second.
We were calling get root with the integer two.
And so node equals two.
And we're checking to see, does the pointer here equal two,
and we find that it doesn't.
So we enter into this while loop and what we're doing here
is we're looking up the grandparent.
So elements of elements of node is this value here
with respect to this, if two is node.
so we're going to update this eight here to seven
and in effect, that's going to be changing the parent
of two from eight to its grandparent seven.
So that's going to give us a structure that looks like this.
Okay. So we've already shortened the path a little bit.
And then we're just going to continue
to follow the path up to the root.
And if we get to the root and nothing gets updated.
So the important thing to notice here
is that two was originally at height three
and now it's at height two.
And every time we do a find operation and we call
this get root method, unless we start at the root
or an immediate child of the root, we're going to shorten
some paths and this way on each call to get root,
the tree may get shorter.
And in the limit, after a great many calls to get root,
we'd expect a very flat tree of height one
with all the child nodes connected directly to the root.
Let's see what happens if we do it again
with find eight three.
Okay, we're going to start here.
We're going to look and see that the parent is seven
but the grandparent or sorry, the parent is zero
but the grandparent is seven.
So we're gonna update the parent of eight to be seven.
And we're going to get this kind of structure here.
And then it's just one more step and we're done.
So again, every time we do a find operation
we're very likely to shorten the path somewhere.
That's path compression.
And it only costs us this one extra line of code.
We're doing a lookup in a vector
which takes place in constant time.
We're doing an assignment
which takes place in constant time.
That's a constant time operation.
We're only adding constant time to the process.
So it's not very expensive at all.
And cumulatively, this will tend to flatten the tree.
So in summary, with way to quick union or path compression
we get a worst case, worst case of big O of M log N
for M operations on a set of N objects.
And we can combine these two methods.
If we combine the two methods with weighted quick union
and path compression, we get big O of M log star N.
Now you've probably not seen log star before.
It's what's called the iterated logarithm.
And the iterated logarithm is the number
of times the logarithm function must be iteratively applied
before the result is less than or equal to one.
So imagine you have some big number and you take the log
and you check to see, is it one or less than one?
No, then you take the log again and you keep doing that
until you get to one or something less than one.
And the iterated logarithm function grows
very very slowly as you might imagine,
because as N is growing exponentially, log N
is just stepping along one step at a time.
So this performance big O of M log star N
is very close to being linear.
With two simple observations, this led us
to weighted unions and path compressions.
And while we can achieve performance
that's not quite linear, it's really close to being linear.
And I don't know about you
but I think those are some pretty neat tricks.
So I'm going to finish up here with just a table
showing you what the iterated logarithm function looks like.
And you can see that two has to grow very large
in order for log star of N to get to four.
And by the time we get to log star of N equals five,
this number here is way bigger than the total number
of particles in the observable universe.
Any number you can possibly think of
I guarantee it's smaller than this number here.
So that's it for now.
Oh, no, there is one more thing.
Let me do one more thing I want to show you.
Just a second.
What I did to prove my point here is I coded up
these classes and I wrote a little comparison.
You've seen this code that generates random numbers
and you've also seen some timer code
and I'm just applying it
to three identical cases of quick union,
quick union weighted and quick union with path compression.
And so I'm timing each of these observations,
one for each type and I'm reporting the duration
that it took in microseconds and the number of sets
just to make sure we're doing everything right.
I did add a little extra bookkeeping here
to keep track of the total number of sets that we have.
As we combine sets, we get fewer and fewer sets.
So if I run this comparison, give it a second.
Oops. There you go.
There we go.
There we are.
So quick union by itself takes
a little under 6 million microseconds.
This should be labeled weighted but it takes
when we add the weighted union
we go from approximately 6 million microseconds
down to 24,000 microseconds.
That's a huge performance improvement.
If we just use path compression,
that gets us down to a little over 17,000 microseconds.
So you can see each one of these
is a progressive improvement.
If we were to combine these two, we'd get even more
of an improvement and I'll leave that up to you.
If you guys want to tinker around
I'll post the code on Blackboard.
Anyhow, that concludes our discussion
of the dynamic equivalence problem and disjoint sets
and how some very simple observations
lead us to some very clever tricks to speed this up
and get us really, really close to linear time performance.
See you next time.
Thanks. Bye bye.