1
00:00:01,562 --> 00:00:03,020
- Hey, how you doing?

2
00:00:03,020 --> 00:00:06,300
So we're going to continue our discussion

3
00:00:06,300 --> 00:00:10,650
about dynamic equivalence, the
dynamic equivalence problem

4
00:00:10,650 --> 00:00:14,163
and the implementation that
makes use of disjoint sets.

5
00:00:15,200 --> 00:00:18,930
And we're going to talk about
two things, weighted union

6
00:00:18,930 --> 00:00:22,540
and path compression, and those
are both ways of speeding up

7
00:00:22,540 --> 00:00:27,540
this implementation that
we started in last video.

8
00:00:28,880 --> 00:00:31,030
So let's take a step back real quick

9
00:00:31,030 --> 00:00:32,370
and restate the problem.

10
00:00:32,370 --> 00:00:36,910
The dynamic equivalence
problem is that we're working

11
00:00:36,910 --> 00:00:40,830
with a collection of objects
and we'd like to do two things.

12
00:00:40,830 --> 00:00:42,440
We'd like to be able to determine

13
00:00:42,440 --> 00:00:44,560
if two objects are related to one another.

14
00:00:44,560 --> 00:00:46,850
That is by some equivalence relation.

15
00:00:46,850 --> 00:00:49,660
So we're asking the
question, do they belong

16
00:00:49,660 --> 00:00:53,740
in the same set, which is
disjoint from all of the sets.

17
00:00:53,740 --> 00:00:56,220
And we'd like to also be
able to connect objects

18
00:00:56,220 --> 00:00:59,230
to join them up by
introducing some equivalence.

19
00:00:59,230 --> 00:01:03,473
And we do that. That's
essentially by merging sets.

20
00:01:04,670 --> 00:01:06,750
We'd like to be able to
do both of those things

21
00:01:06,750 --> 00:01:09,610
as quickly and as efficiently as possible.

22
00:01:09,610 --> 00:01:12,150
And that's the dynamic
equivalence problem.

23
00:01:12,150 --> 00:01:15,600
And we saw in the previous
video that there's a trade-off.

24
00:01:15,600 --> 00:01:20,137
We tried optimizing for
find and we were able

25
00:01:21,870 --> 00:01:25,800
to implement find in
constant time at the cost

26
00:01:25,800 --> 00:01:30,110
of making our union operation
a linear time operation

27
00:01:30,110 --> 00:01:32,120
which we found unsatisfactory.

28
00:01:32,120 --> 00:01:36,340
And so we started working
on optimizing for union

29
00:01:36,340 --> 00:01:39,370
to see if we could get
better performance that way.

30
00:01:39,370 --> 00:01:42,400
And we got ourselves into
a little bit of a pickle.

31
00:01:42,400 --> 00:01:47,400
So just to recap, we have that find method

32
00:01:48,380 --> 00:01:50,400
that's determining whether
or not two elements

33
00:01:50,400 --> 00:01:52,010
are equivalent and the union

34
00:01:52,010 --> 00:01:54,373
which is merging two equivalence classes.

35
00:01:56,130 --> 00:01:58,750
And this is about where
we left off with the code.

36
00:01:58,750 --> 00:02:02,443
We have three methods,
get root, find and unite.

37
00:02:03,780 --> 00:02:07,330
And again, we tried to optimize for union

38
00:02:07,330 --> 00:02:08,540
but there's a catch.

39
00:02:08,540 --> 00:02:09,763
What's the catch?

40
00:02:10,801 --> 00:02:12,250
Well, we see that both find

41
00:02:12,250 --> 00:02:16,650
and unite make two calls to get root.

42
00:02:16,650 --> 00:02:19,290
So their performance is dependent

43
00:02:19,290 --> 00:02:21,320
on the performance of get root.

44
00:02:21,320 --> 00:02:22,730
If get root is slow

45
00:02:22,730 --> 00:02:25,253
both find and unite are going to be slow.

46
00:02:26,100 --> 00:02:29,190
So the limiting factor here
is the time that it takes

47
00:02:29,190 --> 00:02:30,393
to find the root.

48
00:02:31,400 --> 00:02:35,570
And if you'll recall to
find the root of any element

49
00:02:35,570 --> 00:02:37,640
we would start at that element

50
00:02:37,640 --> 00:02:42,380
and we would trace steps back to the root

51
00:02:42,380 --> 00:02:45,363
by following pointers to
the individual parents.

52
00:02:47,427 --> 00:02:49,670
And if the path is short, that's great.

53
00:02:49,670 --> 00:02:51,650
It performs very well.

54
00:02:51,650 --> 00:02:56,650
But as we saw in the earlier video,

55
00:02:57,090 --> 00:02:59,113
some of these paths can get pretty long.

56
00:03:00,050 --> 00:03:02,310
For example, we saw this structure here

57
00:03:02,310 --> 00:03:07,310
on the right that grew
to have a height of four.

58
00:03:08,410 --> 00:03:11,060
There were four edges we have to traverse

59
00:03:11,060 --> 00:03:13,103
from the most distant leaf to the root.

60
00:03:14,480 --> 00:03:17,190
And there aren't that many elements here.

61
00:03:17,190 --> 00:03:21,790
So you can imagine that
if we have a large N

62
00:03:21,790 --> 00:03:24,000
and we've performed a
large number of unions

63
00:03:24,000 --> 00:03:27,580
that we could get a
tree that's pretty tall.

64
00:03:27,580 --> 00:03:30,500
And the longer the path,
the longer it takes

65
00:03:30,500 --> 00:03:32,763
to find the root and there's our problem.

66
00:03:34,430 --> 00:03:37,470
So while the union itself,
the merging of the sets

67
00:03:37,470 --> 00:03:40,080
takes place in constant
time, the union method

68
00:03:40,080 --> 00:03:42,240
has to call get root to figure out

69
00:03:42,240 --> 00:03:44,480
what roots it wants to merge.

70
00:03:44,480 --> 00:03:47,030
So if get root has linear complexity

71
00:03:47,030 --> 00:03:51,400
then that places the limit
on union and on find.

72
00:03:51,400 --> 00:03:56,400
So if get root has a linear complexity

73
00:03:56,800 --> 00:03:58,360
we certainly can't do better

74
00:03:58,360 --> 00:04:00,840
than linear complexity with find or union.

75
00:04:00,840 --> 00:04:04,060
That's not possible.

76
00:04:04,060 --> 00:04:08,270
So here we have the
situation that linear time

77
00:04:08,270 --> 00:04:10,780
for find, we've got linear time for union.

78
00:04:10,780 --> 00:04:12,790
And that means that we have a worst case

79
00:04:12,790 --> 00:04:15,900
for M operations of big O of N times N

80
00:04:15,900 --> 00:04:20,240
and with M approximating N
that's big O of N squared

81
00:04:20,240 --> 00:04:22,760
and N squared, as we've
said before, is yucky.

82
00:04:22,760 --> 00:04:25,170
We don't want that. That's too slow.

83
00:04:25,170 --> 00:04:27,660
Particularly when we have a large number

84
00:04:27,660 --> 00:04:30,130
of elements that we want to merge

85
00:04:30,130 --> 00:04:31,600
which is entirely plausible

86
00:04:31,600 --> 00:04:35,443
given the memory capacity
of modern computers.

87
00:04:36,420 --> 00:04:38,040
So what do we do?

88
00:04:38,040 --> 00:04:39,613
We've got to speed things up.

89
00:04:40,790 --> 00:04:45,010
Well the obvious thing,
shorten the paths to the root,

90
00:04:45,010 --> 00:04:46,110
but how do we do that?

91
00:04:48,000 --> 00:04:51,030
So we're going to see two
approaches that are both based

92
00:04:51,030 --> 00:04:53,490
on very simple observations.

93
00:04:53,490 --> 00:04:56,510
The first approach considers
why we get long paths

94
00:04:56,510 --> 00:04:59,780
in the first place, why do
we have these tall trees?

95
00:04:59,780 --> 00:05:02,130
And it tries to avoid making tall trees.

96
00:05:02,130 --> 00:05:02,963
That makes sense.

97
00:05:02,963 --> 00:05:06,160
You don't want to tall
trees, try not to make them.

98
00:05:06,160 --> 00:05:10,210
The second approach
considers what we can do

99
00:05:10,210 --> 00:05:12,520
to shorten paths that already exists.

100
00:05:12,520 --> 00:05:17,000
So we have these paths and
we have to do this stepping

101
00:05:17,000 --> 00:05:18,970
to find our way back to the root.

102
00:05:18,970 --> 00:05:23,870
Maybe we can do something while
we're tracing that path back

103
00:05:23,870 --> 00:05:27,700
to the root, to speed things
up by shortening those paths.

104
00:05:27,700 --> 00:05:29,670
And that's called path compression.

105
00:05:29,670 --> 00:05:32,070
We'll see that in the
second half of this video.

106
00:05:32,920 --> 00:05:35,500
But first let's start with weighted union.

107
00:05:35,500 --> 00:05:38,040
Again, this has to do with the question

108
00:05:38,040 --> 00:05:39,523
of what makes our trees tall.

109
00:05:41,750 --> 00:05:44,880
Instead of tall trees, we want wide trees,

110
00:05:44,880 --> 00:05:46,790
we want flat trees.

111
00:05:46,790 --> 00:05:51,450
We want balanced trees that
don't have these long paths.

112
00:05:51,450 --> 00:05:53,533
So how do we do that?

113
00:05:55,600 --> 00:05:57,330
You recall from the previous video

114
00:05:57,330 --> 00:06:01,100
we had this state where
we had five disjoint sets.

115
00:06:01,100 --> 00:06:04,330
We had this set here rooted
at one, it has three elements.

116
00:06:04,330 --> 00:06:07,160
We have this set here,
that's rooted at seven,

117
00:06:07,160 --> 00:06:08,300
it's got six elements.

118
00:06:08,300 --> 00:06:10,500
And then we have three
singletons over here.

119
00:06:13,060 --> 00:06:15,390
Now what happens if we perform a union

120
00:06:15,390 --> 00:06:17,600
say of eight and three?

121
00:06:17,600 --> 00:06:19,178
Well, okay.

122
00:06:19,178 --> 00:06:20,480
We're going to take a look at three

123
00:06:20,480 --> 00:06:23,270
and we're going to see
that its parent is one.

124
00:06:23,270 --> 00:06:25,090
We trace that back to one.

125
00:06:25,090 --> 00:06:27,740
We find that one's parent
is one, one equals one.

126
00:06:27,740 --> 00:06:31,743
That must be a root.
So three's root is one.

127
00:06:32,790 --> 00:06:36,723
One is the representative
for that equivalence class.

128
00:06:37,750 --> 00:06:38,990
What about eight?

129
00:06:38,990 --> 00:06:41,610
Well, eight points to zero,

130
00:06:41,610 --> 00:06:44,700
zero points to seven, seven equals seven.

131
00:06:44,700 --> 00:06:47,010
So seven must be the root.

132
00:06:47,010 --> 00:06:51,970
And so seven is the root
associated with node eight.

133
00:06:51,970 --> 00:06:55,473
And that's the representative
for that equivalence class.

134
00:06:56,490 --> 00:06:59,890
Now, according to the algorithm
as we've written it so far,

135
00:06:59,890 --> 00:07:02,520
what we would do next
is we would essentially

136
00:07:02,520 --> 00:07:06,410
graft this tree onto this root.

137
00:07:06,410 --> 00:07:08,680
We would make seven a child of one.

138
00:07:08,680 --> 00:07:13,680
We would update the pointer
here from seven to one.

139
00:07:15,390 --> 00:07:17,433
It's also joining these two trees.

140
00:07:18,350 --> 00:07:23,163
But if we do that, we get this structure,

141
00:07:24,290 --> 00:07:27,030
which if you may have noticed

142
00:07:27,030 --> 00:07:31,130
we just grew the height
of our tree by one.

143
00:07:31,130 --> 00:07:33,730
We went from a tree that was,

144
00:07:33,730 --> 00:07:36,200
well we went from a tree
that was of height one

145
00:07:36,200 --> 00:07:38,870
and a tree that was was of height three

146
00:07:38,870 --> 00:07:41,423
to a combined tree of height four.

147
00:07:43,910 --> 00:07:48,910
And that's if we make this
node here a child of this root,

148
00:07:51,600 --> 00:07:53,410
but what if we were to
do it the other way,

149
00:07:53,410 --> 00:07:54,330
what would happen?

150
00:07:54,330 --> 00:07:56,730
Well, we'd get a structure
that looks like this.

151
00:07:57,720 --> 00:08:00,310
Now here, you see this was the other root.

152
00:08:00,310 --> 00:08:03,130
And we changed that
pointer to point to seven

153
00:08:03,130 --> 00:08:05,750
and seven becomes the
root for the whole thing.

154
00:08:05,750 --> 00:08:08,470
And now we have a tree interestingly,

155
00:08:08,470 --> 00:08:11,313
that still has a height of three.

156
00:08:12,210 --> 00:08:14,760
So in this case, all the
elements are correctly

157
00:08:14,760 --> 00:08:19,573
in the same set, but now the
height of the tree is three.

158
00:08:20,690 --> 00:08:22,140
Oh, what happened?

159
00:08:22,140 --> 00:08:26,120
Well, in the first instance,
we grafted the taller tree

160
00:08:26,120 --> 00:08:28,843
onto the shorter tree and
our height grew by one.

161
00:08:29,790 --> 00:08:32,730
In this instance, we've
grafted the shorter tree

162
00:08:32,730 --> 00:08:35,633
onto the taller tree and
the height is unchanged.

163
00:08:37,200 --> 00:08:41,540
Now we can't go around calculating
the height of these trees

164
00:08:41,540 --> 00:08:44,780
every time we want to do
another union operation.

165
00:08:44,780 --> 00:08:46,560
Calculating the height of a tree

166
00:08:46,560 --> 00:08:48,730
is kind of a costly operation.

167
00:08:48,730 --> 00:08:50,640
And we don't want to burden things

168
00:08:50,640 --> 00:08:53,180
with that calculation.

169
00:08:53,180 --> 00:08:56,350
So what we want to do is
we want to find something

170
00:08:56,350 --> 00:09:00,510
that's quick and easy, not
computationally intensive.

171
00:09:00,510 --> 00:09:03,700
It doesn't really add
anything to our process

172
00:09:03,700 --> 00:09:06,090
but it allows us to make good guesses

173
00:09:06,090 --> 00:09:08,593
about how we should join these two trees.

174
00:09:10,110 --> 00:09:12,750
What we want is something
that's a quick and easy way

175
00:09:12,750 --> 00:09:16,720
to reduce the likelihood
of grafting a taller tree

176
00:09:16,720 --> 00:09:18,250
onto a shorter tree.

177
00:09:18,250 --> 00:09:21,030
So can you think of what that might be?

178
00:09:21,030 --> 00:09:22,183
Let's take a step back.

179
00:09:26,090 --> 00:09:28,840
Without calculating the
height of each tree,

180
00:09:28,840 --> 00:09:31,900
we could simply keep track
of the number of elements

181
00:09:31,900 --> 00:09:35,180
or nodes in each tree and that can be done

182
00:09:35,180 --> 00:09:37,023
with some very simple bookkeeping.

183
00:09:37,870 --> 00:09:40,130
Then when performing union we'd always set

184
00:09:40,130 --> 00:09:42,570
the root of the tree with fewer nodes

185
00:09:42,570 --> 00:09:45,233
to be the root of the
tree with more nodes.

186
00:09:48,150 --> 00:09:51,910
So here we have a tree with three nodes.

187
00:09:51,910 --> 00:09:55,900
Here we have a tree with six nodes.

188
00:09:55,900 --> 00:09:59,990
And so that would tell us
to attach the smaller tree

189
00:09:59,990 --> 00:10:03,920
to the larger by setting
the root of the smaller tree

190
00:10:03,920 --> 00:10:06,800
to point to the root the larger tree.

191
00:10:06,800 --> 00:10:09,140
That gives us this alternative structure

192
00:10:09,140 --> 00:10:11,980
which is shallower. It
has a depth of three.

193
00:10:11,980 --> 00:10:15,800
We didn't increase the depth
by joining the two trees.

194
00:10:15,800 --> 00:10:17,803
And we have this shorter configuration.

195
00:10:18,690 --> 00:10:21,483
Now, how do we accomplish
this in our code?

196
00:10:24,219 --> 00:10:28,293
Well, here's the start of a
weighted quick union class.

197
00:10:29,180 --> 00:10:31,940
And you'll notice that
it's a little different

198
00:10:31,940 --> 00:10:34,150
than what we've seen before.

199
00:10:34,150 --> 00:10:36,670
We're introducing this new vector here.

200
00:10:36,670 --> 00:10:39,600
I'm calling it sizes. It's
also a vector of ints.

201
00:10:39,600 --> 00:10:43,640
We still have the vector
of ints called elements

202
00:10:43,640 --> 00:10:46,370
where the ints are the
pointers to the parents.

203
00:10:46,370 --> 00:10:49,540
But here we have this
new vector called sizes,

204
00:10:49,540 --> 00:10:53,240
which keep track of
the sizes, makes sense.

205
00:10:53,240 --> 00:10:57,490
And so when we instantiate
an object of this class

206
00:10:57,490 --> 00:10:58,740
we call the constructor.

207
00:10:58,740 --> 00:11:00,960
We pass in the size.

208
00:11:00,960 --> 00:11:04,324
It resizes both vectors to the
same size, and then it goes

209
00:11:04,324 --> 00:11:09,324
and it initializes all of the values

210
00:11:09,510 --> 00:11:11,550
in the sizes vector to one.

211
00:11:11,550 --> 00:11:13,420
Now, why do we do that?

212
00:11:13,420 --> 00:11:15,100
We do that because we're starting off

213
00:11:15,100 --> 00:11:17,810
with a collection of singleton sets.

214
00:11:17,810 --> 00:11:20,950
At the beginning every element

215
00:11:20,950 --> 00:11:23,480
is in its own set of size one.

216
00:11:23,480 --> 00:11:25,830
Every element is its own root.

217
00:11:25,830 --> 00:11:28,293
It's just this one root one leaf tree.

218
00:11:29,490 --> 00:11:32,583
And so that's why we initialize
all the values to one.

219
00:11:34,820 --> 00:11:38,890
Then we also have to make a
change to our unite method.

220
00:11:38,890 --> 00:11:41,690
And the change is pretty simple.

221
00:11:41,690 --> 00:11:46,480
All we have to do is perform
a comparison of the sizes

222
00:11:47,620 --> 00:11:50,390
once we find the roots of the two trees.

223
00:11:50,390 --> 00:11:53,070
So we compare the tree rooted at A

224
00:11:53,070 --> 00:11:58,070
and we compare the tree rooted
at B and we make a decision,

225
00:11:58,390 --> 00:12:02,050
and all we're deciding is which tree

226
00:12:02,050 --> 00:12:04,210
to graft onto the other.

227
00:12:04,210 --> 00:12:09,000
And so if the tree rooted
at A is the smaller,

228
00:12:09,000 --> 00:12:10,480
we'll graph that on B.

229
00:12:10,480 --> 00:12:13,230
And if the tree rooted
to B is the smaller one

230
00:12:13,230 --> 00:12:17,050
or if they're equal, we'll
graph that onto the other.

231
00:12:17,050 --> 00:12:18,913
And that's very simple.

232
00:12:20,240 --> 00:12:22,720
The only other step here you'll notice

233
00:12:22,720 --> 00:12:27,720
is that we have to increment
the size of the tree.

234
00:12:27,870 --> 00:12:30,640
So all we're doing is
we're adding the size

235
00:12:30,640 --> 00:12:34,270
of the smaller tree to
the preexisting size

236
00:12:34,270 --> 00:12:35,823
of the larger tree.

237
00:12:36,780 --> 00:12:40,000
Notice that we only have to do this once.

238
00:12:40,000 --> 00:12:42,010
There's no need to update anything else

239
00:12:42,010 --> 00:12:43,840
since all that matters is the number

240
00:12:43,840 --> 00:12:45,800
of the elements in the
newly combined tree.

241
00:12:45,800 --> 00:12:48,370
So we don't have to go
through all of the tree

242
00:12:48,370 --> 00:12:53,170
and update all of the sizes
of all of the sub trees.

243
00:12:53,170 --> 00:12:55,170
We just need to keep track of that root.

244
00:12:56,060 --> 00:12:59,300
And you might wonder why
that's okay to do that.

245
00:12:59,300 --> 00:13:04,300
Well, we have no method
that breaks the trees apart.

246
00:13:04,570 --> 00:13:08,060
We only have a find and
we only have a union.

247
00:13:08,060 --> 00:13:10,253
So once two trees are joined,

248
00:13:11,710 --> 00:13:13,150
we're never going to break them apart.

249
00:13:13,150 --> 00:13:16,880
So once a node that was once a root,

250
00:13:16,880 --> 00:13:19,280
and they all started out as roots,

251
00:13:19,280 --> 00:13:22,300
once a node that was once
a root is no longer a root

252
00:13:22,300 --> 00:13:24,070
it will never become a root again.

253
00:13:24,070 --> 00:13:27,423
So we can just ignore the
value that might be there.

254
00:13:28,360 --> 00:13:30,350
So we only have to make this one addition.

255
00:13:30,350 --> 00:13:33,190
Addition takes place in constant time

256
00:13:33,190 --> 00:13:35,993
and we have a very simple operation here.

257
00:13:37,400 --> 00:13:41,693
Now it's true that we have
to initialize the array,

258
00:13:42,650 --> 00:13:44,630
but the cost of that initialization

259
00:13:44,630 --> 00:13:47,700
is amortized over all future operations.

260
00:13:47,700 --> 00:13:52,410
So that becomes trivial and
the updating of the sizes

261
00:13:52,410 --> 00:13:54,413
as I said, takes place in constant time.

262
00:13:55,550 --> 00:13:58,350
But what effect does that have
on the height of the trees

263
00:13:58,350 --> 00:14:00,880
and the time it takes to find the root?

264
00:14:00,880 --> 00:14:03,550
Well by using this approach

265
00:14:03,550 --> 00:14:06,380
the maximum height of
a tree becomes log N.

266
00:14:06,380 --> 00:14:10,240
And so we wind up with
performance like this.

267
00:14:10,240 --> 00:14:14,680
If the height of the tree is log N,

268
00:14:14,680 --> 00:14:18,990
then we can't possibly
have a find root operation

269
00:14:18,990 --> 00:14:23,740
that takes more than log N
steps because all that's doing

270
00:14:23,740 --> 00:14:26,540
is counting, or I shouldn't say counting,

271
00:14:26,540 --> 00:14:28,720
I should say taking those steps

272
00:14:28,720 --> 00:14:31,740
from the child to the
parent, up to the root.

273
00:14:31,740 --> 00:14:36,680
And if the tallest tree we
can make is of log N size

274
00:14:36,680 --> 00:14:38,720
then we can't take more than log N steps

275
00:14:38,720 --> 00:14:41,483
to get to the root from
even the most distant leaf.

276
00:14:42,470 --> 00:14:46,900
So now, now we have find
and union operations

277
00:14:47,930 --> 00:14:50,920
that have a complexity of big O of log N,

278
00:14:50,920 --> 00:14:54,880
and that's a big
improvement over big O of N.

279
00:14:54,880 --> 00:14:55,983
Log N is sublinear.

280
00:14:57,330 --> 00:15:00,610
And you'll notice that the
worst case for M operations

281
00:15:00,610 --> 00:15:04,920
which was approximating
a big O of N squared

282
00:15:04,920 --> 00:15:06,850
is now big O of N log N.

283
00:15:06,850 --> 00:15:09,000
And that again is a big improvement.

284
00:15:09,000 --> 00:15:11,340
And this is resulted from a very

285
00:15:11,340 --> 00:15:15,093
very simple operation or
observation I should say,

286
00:15:16,330 --> 00:15:19,940
that we were producing
these these long paths

287
00:15:19,940 --> 00:15:21,783
and we did this very simple thing.

288
00:15:23,340 --> 00:15:26,150
It's not precise, it's not guaranteed,

289
00:15:26,150 --> 00:15:28,930
but in the main it will give us

290
00:15:28,930 --> 00:15:32,023
wider, fatter, shorter trees.

291
00:15:33,080 --> 00:15:34,463
And that's kind of cool.

292
00:15:35,330 --> 00:15:38,810
So now the next question
is, can we do better?

293
00:15:38,810 --> 00:15:41,860
And again, the answer is yes

294
00:15:41,860 --> 00:15:45,320
based on another simple observation.

295
00:15:45,320 --> 00:15:47,283
So let's move on to path compression.

296
00:15:51,500 --> 00:15:54,200
As I said, this technique
is called path compression

297
00:15:54,200 --> 00:15:59,200
and let's consider this problem instance.

298
00:15:59,320 --> 00:16:03,280
Again, we have this
tree here rooted at one,

299
00:16:03,280 --> 00:16:05,580
the tree rooted at seven
and a few singletons.

300
00:16:07,060 --> 00:16:11,100
And let's say we want
to perform the operation

301
00:16:11,100 --> 00:16:12,803
find two, three.

302
00:16:15,650 --> 00:16:17,180
Two is here. Three is here.

303
00:16:17,180 --> 00:16:20,050
That's a quick and easy
one, three points to one.

304
00:16:20,050 --> 00:16:21,680
One's a root, we're done.

305
00:16:21,680 --> 00:16:23,770
Okay. So let's take a
look at this longer path

306
00:16:23,770 --> 00:16:25,070
and see what happens here.

307
00:16:26,010 --> 00:16:31,010
So as we step from node to
node until we get to the root,

308
00:16:35,610 --> 00:16:40,050
we're traversing this path
and there might be a way

309
00:16:40,050 --> 00:16:43,453
that we can shorten the
path or part of the path.

310
00:16:44,950 --> 00:16:47,200
So let's take a look at
the little code here.

311
00:16:48,670 --> 00:16:52,730
This is the same get root
function that we had before.

312
00:16:52,730 --> 00:16:55,770
Except I've added this one line here.

313
00:16:55,770 --> 00:16:59,833
Elements sub node equals
elements sub elements of node.

314
00:17:00,670 --> 00:17:02,260
What is that doing?

315
00:17:02,260 --> 00:17:04,060
Let's think about this for a second.

316
00:17:04,930 --> 00:17:09,737
We were calling get root
with the integer two.

317
00:17:11,160 --> 00:17:14,000
And so node equals two.

318
00:17:14,000 --> 00:17:17,807
And we're checking to see, does
the pointer here equal two,

319
00:17:17,807 --> 00:17:19,330
and we find that it doesn't.

320
00:17:19,330 --> 00:17:23,870
So we enter into this while
loop and what we're doing here

321
00:17:23,870 --> 00:17:26,280
is we're looking up the grandparent.

322
00:17:26,280 --> 00:17:31,280
So elements of elements
of node is this value here

323
00:17:32,640 --> 00:17:36,500
with respect to this, if two is node.

324
00:17:36,500 --> 00:17:41,500
so we're going to update
this eight here to seven

325
00:17:43,000 --> 00:17:46,930
and in effect, that's going
to be changing the parent

326
00:17:46,930 --> 00:17:50,763
of two from eight to
its grandparent seven.

327
00:17:52,000 --> 00:17:55,693
So that's going to give us a
structure that looks like this.

328
00:17:57,090 --> 00:18:00,123
Okay. So we've already
shortened the path a little bit.

329
00:18:01,470 --> 00:18:03,550
And then we're just going to continue

330
00:18:03,550 --> 00:18:06,800
to follow the path up to the root.

331
00:18:06,800 --> 00:18:11,800
And if we get to the root
and nothing gets updated.

332
00:18:12,250 --> 00:18:16,690
So the important thing to notice here

333
00:18:16,690 --> 00:18:19,090
is that two was originally at height three

334
00:18:19,090 --> 00:18:21,230
and now it's at height two.

335
00:18:21,230 --> 00:18:24,980
And every time we do a
find operation and we call

336
00:18:24,980 --> 00:18:29,980
this get root method,
unless we start at the root

337
00:18:30,010 --> 00:18:32,800
or an immediate child of the
root, we're going to shorten

338
00:18:32,800 --> 00:18:36,820
some paths and this way
on each call to get root,

339
00:18:36,820 --> 00:18:38,830
the tree may get shorter.

340
00:18:38,830 --> 00:18:42,120
And in the limit, after a
great many calls to get root,

341
00:18:42,120 --> 00:18:45,050
we'd expect a very flat tree of height one

342
00:18:45,050 --> 00:18:48,393
with all the child nodes
connected directly to the root.

343
00:18:52,680 --> 00:18:55,290
Let's see what happens if we do it again

344
00:18:55,290 --> 00:18:58,153
with find eight three.

345
00:18:59,180 --> 00:19:01,930
Okay, we're going to start here.

346
00:19:01,930 --> 00:19:05,290
We're going to look and see
that the parent is seven

347
00:19:05,290 --> 00:19:08,160
but the grandparent or
sorry, the parent is zero

348
00:19:08,160 --> 00:19:09,920
but the grandparent is seven.

349
00:19:09,920 --> 00:19:14,480
So we're gonna update the
parent of eight to be seven.

350
00:19:14,480 --> 00:19:18,860
And we're going to get this
kind of structure here.

351
00:19:18,860 --> 00:19:21,683
And then it's just one
more step and we're done.

352
00:19:23,070 --> 00:19:26,050
So again, every time
we do a find operation

353
00:19:26,050 --> 00:19:29,890
we're very likely to
shorten the path somewhere.

354
00:19:29,890 --> 00:19:31,363
That's path compression.

355
00:19:32,460 --> 00:19:36,190
And it only costs us this
one extra line of code.

356
00:19:36,190 --> 00:19:40,190
We're doing a lookup in a vector

357
00:19:40,190 --> 00:19:42,570
which takes place in constant time.

358
00:19:42,570 --> 00:19:43,670
We're doing an assignment

359
00:19:43,670 --> 00:19:45,890
which takes place in constant time.

360
00:19:45,890 --> 00:19:47,470
That's a constant time operation.

361
00:19:47,470 --> 00:19:49,870
We're only adding constant
time to the process.

362
00:19:49,870 --> 00:19:52,913
So it's not very expensive at all.

363
00:19:55,040 --> 00:19:57,793
And cumulatively, this will
tend to flatten the tree.

364
00:20:00,240 --> 00:20:04,420
So in summary, with way to
quick union or path compression

365
00:20:04,420 --> 00:20:09,420
we get a worst case, worst
case of big O of M log N

366
00:20:11,330 --> 00:20:15,933
for M operations on a set of N objects.

367
00:20:17,750 --> 00:20:19,560
And we can combine these two methods.

368
00:20:19,560 --> 00:20:24,560
If we combine the two methods
with weighted quick union

369
00:20:26,010 --> 00:20:30,430
and path compression, we
get big O of M log star N.

370
00:20:30,430 --> 00:20:34,200
Now you've probably not
seen log star before.

371
00:20:34,200 --> 00:20:37,730
It's what's called the iterated logarithm.

372
00:20:37,730 --> 00:20:40,680
And the iterated logarithm is the number

373
00:20:40,680 --> 00:20:44,820
of times the logarithm function
must be iteratively applied

374
00:20:44,820 --> 00:20:48,840
before the result is less
than or equal to one.

375
00:20:48,840 --> 00:20:53,040
So imagine you have some big
number and you take the log

376
00:20:53,040 --> 00:20:55,930
and you check to see, is
it one or less than one?

377
00:20:55,930 --> 00:20:59,560
No, then you take the log
again and you keep doing that

378
00:20:59,560 --> 00:21:02,143
until you get to one or
something less than one.

379
00:21:04,000 --> 00:21:07,040
And the iterated logarithm function grows

380
00:21:07,040 --> 00:21:09,480
very very slowly as you might imagine,

381
00:21:09,480 --> 00:21:13,623
because as N is growing
exponentially, log N

382
00:21:14,930 --> 00:21:18,113
is just stepping along one step at a time.

383
00:21:19,330 --> 00:21:23,330
So this performance big O of M log star N

384
00:21:23,330 --> 00:21:25,903
is very close to being linear.

385
00:21:27,260 --> 00:21:30,640
With two simple observations, this led us

386
00:21:30,640 --> 00:21:33,400
to weighted unions and path compressions.

387
00:21:33,400 --> 00:21:36,020
And while we can achieve performance

388
00:21:36,020 --> 00:21:40,720
that's not quite linear, it's
really close to being linear.

389
00:21:40,720 --> 00:21:41,680
And I don't know about you

390
00:21:41,680 --> 00:21:44,600
but I think those are
some pretty neat tricks.

391
00:21:44,600 --> 00:21:49,550
So I'm going to finish
up here with just a table

392
00:21:49,550 --> 00:21:52,763
showing you what the iterated
logarithm function looks like.

393
00:21:53,630 --> 00:21:58,330
And you can see that two
has to grow very large

394
00:21:58,330 --> 00:22:03,330
in order for log star of N to get to four.

395
00:22:03,810 --> 00:22:08,140
And by the time we get to
log star of N equals five,

396
00:22:08,140 --> 00:22:11,790
this number here is way
bigger than the total number

397
00:22:11,790 --> 00:22:14,563
of particles in the observable universe.

398
00:22:16,508 --> 00:22:18,440
Any number you can possibly think of

399
00:22:18,440 --> 00:22:21,510
I guarantee it's smaller
than this number here.

400
00:22:21,510 --> 00:22:24,810
So that's it for now.

401
00:22:24,810 --> 00:22:27,140
Oh, no, there is one more thing.

402
00:22:27,140 --> 00:22:30,060
Let me do one more thing
I want to show you.

403
00:22:30,060 --> 00:22:30,973
Just a second.

404
00:22:33,790 --> 00:22:38,790
What I did to prove my
point here is I coded up

405
00:22:39,070 --> 00:22:42,960
these classes and I wrote
a little comparison.

406
00:22:42,960 --> 00:22:47,960
You've seen this code that
generates random numbers

407
00:22:50,500 --> 00:22:54,160
and you've also seen some timer code

408
00:22:54,160 --> 00:22:55,710
and I'm just applying it

409
00:22:55,710 --> 00:23:00,670
to three identical cases of quick union,

410
00:23:00,670 --> 00:23:04,760
quick union weighted and quick
union with path compression.

411
00:23:04,760 --> 00:23:07,233
And so I'm timing each
of these observations,

412
00:23:09,790 --> 00:23:14,790
one for each type and I'm
reporting the duration

413
00:23:16,500 --> 00:23:20,060
that it took in microseconds
and the number of sets

414
00:23:20,060 --> 00:23:22,390
just to make sure we're
doing everything right.

415
00:23:22,390 --> 00:23:25,440
I did add a little extra bookkeeping here

416
00:23:25,440 --> 00:23:28,710
to keep track of the total
number of sets that we have.

417
00:23:28,710 --> 00:23:32,050
As we combine sets, we
get fewer and fewer sets.

418
00:23:32,050 --> 00:23:35,603
So if I run this comparison,
give it a second.

419
00:23:41,630 --> 00:23:43,490
Oops. There you go.

420
00:23:43,490 --> 00:23:44,323
There we go.

421
00:23:49,270 --> 00:23:50,790
There we are.

422
00:23:50,790 --> 00:23:55,790
So quick union by itself takes

423
00:23:55,990 --> 00:23:58,923
a little under 6 million microseconds.

424
00:24:00,390 --> 00:24:05,370
This should be labeled
weighted but it takes

425
00:24:05,370 --> 00:24:09,441
when we add the weighted union

426
00:24:09,441 --> 00:24:13,430
we go from approximately
6 million microseconds

427
00:24:13,430 --> 00:24:16,340
down to 24,000 microseconds.

428
00:24:16,340 --> 00:24:19,670
That's a huge performance improvement.

429
00:24:19,670 --> 00:24:22,980
If we just use path compression,

430
00:24:22,980 --> 00:24:27,980
that gets us down to a little
over 17,000 microseconds.

431
00:24:28,870 --> 00:24:30,670
So you can see each one of these

432
00:24:30,670 --> 00:24:32,410
is a progressive improvement.

433
00:24:32,410 --> 00:24:37,410
If we were to combine these
two, we'd get even more

434
00:24:37,570 --> 00:24:40,750
of an improvement and
I'll leave that up to you.

435
00:24:40,750 --> 00:24:42,110
If you guys want to tinker around

436
00:24:42,110 --> 00:24:43,960
I'll post the code on Blackboard.

437
00:24:43,960 --> 00:24:46,700
Anyhow, that concludes our discussion

438
00:24:46,700 --> 00:24:51,700
of the dynamic equivalence
problem and disjoint sets

439
00:24:54,580 --> 00:24:57,390
and how some very simple observations

440
00:24:57,390 --> 00:25:01,640
lead us to some very clever
tricks to speed this up

441
00:25:01,640 --> 00:25:05,723
and get us really, really close
to linear time performance.

442
00:25:06,830 --> 00:25:07,700
See you next time.

443
00:25:07,700 --> 00:25:08,763
Thanks. Bye bye.