[racket-dev] union-find

On Tue, Jan 29, 2013 at 2:51 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> I've just pushed an implementation of the union-find algorithm to the data/
> collection. I didn't do it quite the way wikipedia recommends, but instead
> made the sets be little containers whose canonical element can be mutated.

More code reviewing:

As far as I can tell, the main difference is that in your instance,
there's one less pointer per node.  This is at the cost of a required
runtime type check that can distinguish between boxes and uf-set
instances.

In the Wikipedia example, because each node has a separate parent
pointer field that's guaranteed to point to a node, the lookup doesn't
need as many runtime type-checking capabilities: it just needs memory
equality to tell when to stop hunting upward.  It would require
profiling to determine which strategy is more costly.