0
$\begingroup$

I am studying the Union Find data structure using this material written by Sedgwick et al.

I am specifically interested in the versions they call QuickFindUF, QuickUnionUF, WeightedQuickUnionUF and QuickUnionWithPathCompression and WeightedQuickUnionWithPathCompression.

I was eager to see the difference in their performance, therefore I organized my first experiment as follows: I create, 30000 disjoint components and then I do another 30000 iterations connecting two components, each chosen at random. My first question is: is this a good way to see the difference in their performance? I get the following timings for aforementioned experiments:

Union for <class '__main__.QuickFindUF'>:  Components 30000 Unions 30000 Total time 65.71490097045898
Union for <class '__main__.QuickUnionUF'>:  Components 30000 Unions 30000 Total time 2.9845962524414062
Union for <class '__main__.WeightedQuickUnionFind'>:  Components 30000 Unions 30000 Total time 0.11716842651367188
Union for <class '__main__.QuickUnionWithPathCompressionUF'>:  Components 30000 Unions 30000 Total time 0.13376975059509277
Union for <class '__main__.WeightedQuickUnionWithPathCompressionUF'>: 1 Components 30000 Unions 30000 Total time 0.12238788604736328

Do these results agree well with the theory? I mean naively, the 65 seconds for QuickFind is kind of predictable, since the complexity is linear in number of components. It is also good to see that there is a big difference between QuickUnionUF and its derivatives which are meant to be more efficient. It also makes a lot of sense to me. However, I can not understand, why derivatives of QuickUnionUF do not show big difference in their running times.Is my experiment a poorly designed one? What are the circumstances where the derivatives of QuickUnionUF would perform much better?

Also, I did the following experiment: 30000 components, 30000 random unions and then 100000 times I pick two components at random and check if they are connected. Again, is this a good way to perform this experiment? Here are results:

Connected check <class '__main__.QuickFindUF'>: Components 30000 Unions 30000 Total time 0.29352402687072754
Connected check <class '__main__.QuickUnionUF'>: Components 30000 Unions 30000 Total time 47.74206566810608
Connected check <class '__main__.WeightedQuickUnionFind'>: Components 30000 Unions 30000 Total time 0.3880898952484131
Connected check <class '__main__.QuickUnionWithPathCompressionUF'>: Components 30000 Unions 30000 Total time 0.3855886459350586
Connected check <class '__main__.WeightedQuickUnionWithPathCompressionUF'>: Components 30000 Unions 30000 Total time 0.3770413398742676

Again, for QuickUnion we get the worst results since skewed trees may appear, destroying our worst-case performance. However, is this expected that performance of QuickFindUF(constant complexity for find operation) is more or less the same as the performance of derivatives of QuickUnionUF? Are there circumstances where the performance would be significantly different? Some special cases, non-uniformly distributed union operations and so on?

Another question: should I rather measure the growth of the timings as the input size increases?

Thank you for taking time to read and answer!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.