On Tue, Jan 29, 2013 at 2:51 PM, Robby Findler <[email protected]> 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. _________________________ Racket Developers list: http://lists.racket-lang.org/dev
