[racket-dev] union-find

On Tue, Jan 29, 2013 at 4:23 PM, Danny Yoo <dyoo at hashcollision.org> wrote:

> 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.
>

Oh, no, that's not the difference. I'll change the code to avoid the extra
test.

The difference I see is that union requires a find in the wikipedia
version. I don't understand that, but it might have something to do with
the idea that all objects are somehow automatically singleton sets (maybe?
But that doesn't quite make sense to me either.)

Robby
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20130129/9d1d8c81/attachment-0001.html>