- [Instructor] The dynamic equivalence, problem
and disjoint sets.
In an earlier video, we saw the dynamic equivalence problem.
I'll restate it here.
Say we have a collection of objects,
we'd like to be able to determine
if two objects are related
to one another by some equivalence relation
and we'd like to be able to connect these objects
by introducing and equivalence
and we'd like to be able to perform both of these operations
as quickly and efficiently as possible.
That's the dynamic equivalence problem.
The two operations that we're speaking of
are find and union.
The fine method determines whether or not
two elements are equivalent.
That is, are they members of the same equivalence class
or do they reside in the same set
which is disjoint from all other sets.
The union method,
takes the union of two equivalents classes
effectively merging them
and as we alluded to in the earlier video,
when we're considering the design for this problem
we need to choose an appropriate data structure.
So here we're using an array as a data structure
that represents this problem instance
as a collection of disjoint sets.
How is that?
Well, each element in the vector
indicates the representative of some set.
So we read this,
this is a index zero.
This value is six.
This means that element zero is in the set represented
by the value six.
So we see here's the representative value six,
zero and six are together in the same set
and notice that six is also represented by six.
We've chosen one single representative of each disjoint set.
So again, as we saw in the earlier video,
we can optimize this problem for the find operation
and we can have constant time
that's big of O of one for the fine method
or we can optimize this problem for union
and have a constant time union method
but we can't have both,
like I said in the last video
you can't have your cake and eat it too.
So there's a trade-off,
but it turns out that with a few clever tricks,
we can get pretty close.
So let's start cracking this problem
by taking a look at what it would entail
to optimize for find.
Optimizing for find is a piece of cake.
If we have this data structure
where we choose one representative
for each equivalence class
and label all the elements belonging to the same class
with the value for that representative,
then all we need to do is compare values
and we can do that in constant time.
So for example, are the elements zero and five
in the same equivalence class?
We check the values of those indices.
If the values are the same
then these elements are in the same equivalence class.
If not, then they aren't.
So here, we see the zero and five
are not in the same equivalence class.
Zero is in the equivalence class represented by six
and five is in the equivalence class represented by five.
Now getting a value from a vector takes constant time.
Comparing two values takes constant time.
So this operation can be performed in constant time.
Here's another example,
are two and eight in the same equivalence class?
Well, yeah, we look at the index two,
we see a value three.
We know that two in the class
represented by the value three,
eight also has a three here.
We can see up above that eight and three are connected.
They belong in the same equivalence class.
So this is gonna return true.
Again we're just looking up two values in a vector
that takes place and constant time.
The comparison takes place in constant time.
The whole thing's done in constant time
and this is gonna come as great shock,
here's the code in C++.
I'm not giving all of the surrounding code
but imagine we have some class
and we have some private member field,
a vector of ints called elements
and then here's this method
that returns a Boolean called find.
We take two ints which are indices.
and we look at the values
that we find at those two indices
in our vector elements.
So if these are equivalent,
this is gonna return true.
If they're not equivalent,
it's gonna return false.
Simple as that.
So that's easy.
So now we have a find operation
that runs in constant time
but what about union?
Well, let's say we wanted to connect four and 10.
We'd have to get representative values
for the set containing four
and the set containing 10.
We'd have to choose a new representative
from between those
which we choose doesn't matter
but we do have to choose
and then we have to iterate through the entire array
and update representatives to reflect the new connection.
So let's walk through this example.
We're gonna connect four and 10.
So here now we have four and 10
and the representative of four is four
and the representative of 10 is 11.
So let's choose four as the representative of the new union
and now we have to go through the whole array
and wherever we find an 11,
we have to change it to a four
and there's no other way to do that
besides iterating through the whole array.
So we gotta start at zero,
is that an 11? No.
Is that in 11? No, no, no, no, no.
Until we get down to here
and then we see we found an 11,
we changed it to a four.
We add another 11,
we change it to a four.
That's the process we have to go through.
There was a fair amount of work to be done here,
just changing the representatives.
So while we have a constant time for find,
we have a linear time for union
because we have to iterate that entire vector
and here's what that method might look like.
Again, I'm not supplying the surrounding code.
Here it is in C++.
We've got this unite method
and if two elements aren't already in the same class
we call find first
then we pick one representative,
we call it the target
and the one that we're gonna change,
we call that change
and then we iterate through the entire vector
checking to see if the element at index i
equals the value that we wanna change
and if it does,
then we set it equal to the target
and then we're done.
We do that whole loop.
So again, if two elements aren't already in the same class
we pick one representative,
iterate through the entire array
and update the representatives as needed.
Now as an aside,
notice that we name our method unite.
This is for two reasons.
First is a minor stylistic thing.
We prefer that method names are verbs or begin with verbs
but in this case more importantly,
union is a C++ keyword.
So we can't have a method with the same name.
So we're gonna perform our unions
by calling the unite method
and that makes good sense.
That's a good word for it,
but we've still got this problem.
We have constant time for find and linear time for union
and what if we wanted to perform a lot of operations
on large data sets say m operations.
Our worst case would be O of n times n
and with m approximately equal to n
that's the same as O of n squared.
So we've got a worst case for m operations
where m is approximately equal to n
of all of n squared
and as we've seen O of n squared is pretty yucky.
It's only suitable for small problem instances.
So think about what happens
if we have a million elements in our vector.
On the laptop I'm using right now to make this presentation
it takes about 3,500 microseconds
to iterate and update a vector of a million elements.
At that speed it would take about an hour
to perform a million unions.
That's no good.
So we're gonna have look at some other approaches
to see if we can do better.
So we've optimized for find
and we got stuck there.
Well what happens if we optimize for union.
Now here same problem instance
except we're starting with all of our elements
in their own singleton sets.
We've got our 12 elements.
Each is in its own disjoint set
and we can see this in the vector.
The value for index zero is zero.
The value for index one is one.
The value for index two is two and so on.
For each element,
the value and the index are the same.
Now let's think of these as trees
and sure it's fine to have a tree of a single node
so each one of these is a tree,
perfectly valid tree,
doesn't have any branches,
it only has a root
but that's okay they're trees
and so we have a forest of 12 trees.
When we have a collection of trees
we call it a forest
that should come as no surprise
but it turns out that looking at the problem this way
makes our union operations easy.
When we look at things as trees,
what do I mean by that?
Given a naive approach, we could perform union
by setting the parent of six here to be zero.
We've got union zero six.
Well, let's take six and point that to zero
and we've got a little tree with one branch and a leaf here
and now we have a disjoint set
consisting of zero and six represented as a tree
with zero at the root.
Okay that works.
Under this arrangement,
how would we perform find?
Well, we'd look to see if two elements share the same root
and if they do
then they're in the same disjoint set.
How do we find the root?
Well we just trace that path back
until we find an element whose index
and the value are the same
and that way we know we found a root.
So in this case,
we've got find eight and six.
We start at eight.
We look at the value, the root of eight is eight.
So that's in its own singleton set.
We look at six,
we see that six is pointing to zero.
We follow that back to zero.
We look at zero,
the index and the value are the same.
So that's a root.
So the root of eight is eight,
the root of six zero
and we know that those aren't in the same set, okay?
They're not in the same equivalence class,
but without modification,
this approach can get us into trouble.
Maybe you can anticipate where we're heading with this.
Let's say we do union six, four,
well, here's six
and there's four,
four sitting in its own singleton set
and what we're gonna do
is we're gonna change this four to point to six.
So we get something that looks like this.
Here is four points to six.
We go to six point to zero, zero, okay?
Fine little tree there.
No problem so far,
but what happens now
if we call union with the parameters four and zero.
So if we're going to perform this operation
union four zero,
under the union operation as we've defined it so far
this would result in pointing zero to four
and now we got a problem.
Zero points to four, four points to six, six points to zero
zero points to four
and we've got a loop,
we've got a cycle.
It's no longer a tree.
We have a cycle with no root
and therefore our find operation can't work.
Now it turns out that there's a simple fix
when performing union
instead of just doing this naive connection.
We first find the root of each of the two elements
to be United
and then point the root of one to the root of the other
and that solves our problem.
To take a step back
if we were to were to perform a union,
we'd find that four's route is zero
by tracing this path back
and zero's route is zero
and we'd update zero to point to zero.
That's no change at all
and so in this way we don't form cycles,
but there's a problem now,
we've traded one problem for another.
The performance of union is now dependent
upon the performance of find
and let's keep that in mind
as we walk through another little demonstration.
So let's start over.
We have all of our elements in Singleton sets.
So we have 12 disjoint sets right now
and we're gonna take union zero and six
like we did before.
The root of zero is zero.
The root of six is six.
So we'll set the root of six to be zero.
There we go.
We're good for one step.
Now union seven, four,
we'll just take four,
we'll point it to seven, all good.
Now union eight, two, okay?
We've got two comes over here.
These are of course all still part of the same vector
we're just moving them around
to show how they look like a tree,
but this is still a linear structure.
So two becomes a child of eight
but now what happens if we union six and two?
Here's six, here's two.
Well, we calculate that the root of six is zero
and the root of two was eight
so we make zero the root of eight,
essentially grafting it onto this tree here.
So now these elements are connected in a tree.
They form one disjoint set or equivalence class
and these other guys are out here
sitting in their equivalence classes,
separate from that.
Now let's do union seven, six.
Well, before the parent of six was zero
and the parent of seven is seven.
So we're going to graph that tree
that was rooted at zero onto seven here
now by making seven the parent of zero.
Now we'll union one and three.
Now union three and five
and now union eight and three.
It should be clear at this point
that we have yet another problem.
The union method is dependent on finding the root
and the getRoot method requires tracing a path back
from an element to its root
but now these trees can get pretty tall
and with the tall tree
finding the root can be a costly operation,
here if I wanna find the root of two,
I have to trace back to eight to zero to seven
back to one to find it's root.
So that can be a costly operation.
Let's look at the code.
Here's an implementation.
We have three methods.
Again, I'm not supplying the surrounding code.
Just focus on these.
We have one to get the root of an arbitrary element
we pass in an integer
that indicates the element in question,
we have a while loop and as long as the value
does not equal the index, we keep going.
We keep stepping back until we find the appropriate node
and then we return that node.
The fine method compares the roots
of two arbitrary elements and returns a Boolean.
So here's getRoot a getRoot b.
Are they equal?
Return true or false
and unite finds the root of both elements
and points the root of one tree to the root of the other.
Now we're not done yet
because of the problem we've pointed out.
Union depends on find and find
has to trace paths back to roots
and the trees can get pretty tall.
So while union strictly by itself takes place
in constant time,
the union method requires calling find.
So a find has linear complexity
so does union and this is not satisfactory.
So here we have find takes linear time
and union takes linear time.
So again we have a worst case for m operations
of all of m times n
which is approximately O of n squared
four m approximately equal to n
and it seems like we're right back where we started
but in the next video,
we'll see a couple of neat tricks
as to how we can improve matters.
We're gonna take this optimization for union
and repair it
and we'll wind up with something that operates
in sub linear time.
That's all for now.