[computer-go] Fast data structures for small sets

[Peter Drake <drake@xxxxxxxxxx>]

There's been some talk here about paying too much attention to the 
asymptotic behavior of algorithms, and not enough to the behavior at 
the scales that actually come up in Go.  It struck me that the sets we 
use, such as sets of liberties, are usually quite small (< 10).  I ran 
some experiments on the appropriate data structures for such sets.

I compared four set implementations in Java:  my own implementation of 
ArrayList, java.util.ArrayList, java.util.HashSet, and 
java.util.TreeSet (which is a red-black tree).

First, comparing search times:

This is what we would expect from our first data structures class.  The 
time for TreeSet does grow logarithmically if you plot it by itself, 
but it swamped by the linear-time structures here.

Now, compare traversal times:

For some reason, my (naive) implementation beats all of the built-in 
sets.  I suspect this has to do with some measures that the others take 
in the name of robustness.

So, a proposal:  we spend a lot more time traversing these small sets 
than searching for particular elements, so a simple ArrayList (and 
specifically a very simple implementation) is the way to go.

DISCLAIMERS:  Please no "if you want speed don't use Java" comments.  I 
realize that an ArrayList is not strictly speaking a Set, but that 
doesn't matter for these operations.  These comments do not apply to 
large sets, such as pattern databases.  Not to be taken internally or 
used as a flotation device.

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/