On Jul 20, 2007, at 8:04 AM, Jason House wrote:
I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything.
Yes -- O(log* n) to be precise, as mentioned in my book, <shameless plug>Data Structures and Algorithms in Java</shameless plug>.
Merging chains together with a chain ID approach can be O(#stones) and then O(1) for everything else.
Well, it's O(#stones in smaller chain), with the "smaller" chain heuristically determined as the one with fewer pseudoliberties.
Disjoint sets don't walk the tree for every lookup... the tree is flattened with each lookup.
You still have to perform the tree-walking operation; it's just that with path compression there's *usually* only one step from a stone to the root. With the root explicitly stored, there's also no branching (if statements), which Lew asserts is very important for speed on modern processors.
Peter Drake http://www.lclark.edu/~drake/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
