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
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 email@example.com.
For more options, visit https://groups.google.com/d/optout.