<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Jan 29, 2013 at 4:23 PM, Danny Yoo <span dir="ltr"><<a href="mailto:dyoo@hashcollision.org" target="_blank">dyoo@hashcollision.org</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Tue, Jan 29, 2013 at 2:51 PM, Robby Findler<br> <<a href="mailto:robby@eecs.northwestern.edu">robby@eecs.northwestern.edu</a>> wrote:<br> </div><div class="im">> I've just pushed an implementation of the union-find algorithm to the data/<br> > collection. I didn't do it quite the way wikipedia recommends, but instead<br> > made the sets be little containers whose canonical element can be mutated.<br> <br> </div>More code reviewing:<br> <br> As far as I can tell, the main difference is that in your instance,<br> there's one less pointer per node. This is at the cost of a required<br> runtime type check that can distinguish between boxes and uf-set<br> instances.<br> <br> In the Wikipedia example, because each node has a separate parent<br> pointer field that's guaranteed to point to a node, the lookup doesn't<br> need as many runtime type-checking capabilities: it just needs memory<br> equality to tell when to stop hunting upward. It would require<br> profiling to determine which strategy is more costly.<br> </blockquote><div><br></div><div style>Oh, no, that's not the difference. I'll change the code to avoid the extra test.</div><div style><br></div><div style>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.)</div> <div style><br></div><div style>Robby</div></div></div></div>