This was homework. It has been completed.

I'm doing the SU Algoriths 2 coursera course for fun at the moment. One
of the topics covers union find. In doing an assignment I had a look at
the performance difference between ranked union find with and without
path compression (impls here: http://play.golang.org/p/_TwdiqFfe6 - I
can't post more explicit code here due to the course ToS).

In the assignment input data set (approximately 2e5 unique items to be
clustered using single linkage based on implicit distance) I see no real
difference between the implementations and no improvement (actually
worsens by about 5-10% - actually about as much worse as making the rank
based union pessimal by inverting the rank inequality condition) when I
include path compression.

The clustering is completed in ~3s on my machine (compared to <1s for a
competing C++ implementation - I cannot provide this since it was
written by the CTA and he should not release it publicly).

The timing for the CTA's code is here (averages of 1000 runs of complete

Iterative without path compression: 948ms
Iterative with path compression: 939ms
Recursive without path compression: 951ms
Recursive with path compression: 939ms

So, questions:

      1. What problem size is likely to benefit from path compression?
      2. Clearly the C++ shows some (possibly negligible) improvement.
         What about gc would explain why this is not seen in the Go
         version (I see the opposite)?


You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
postedJul 18, '14 at 12:23a
activeJul 18, '14 at 12:23a

1 user in discussion

Dan Kortschak: 1 post



site design / logo © 2021 Grokbase