Re: Bitmaps vs Lists

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I use linked lists of 16 bit integers as my most basic
data structure.  Many of the lists are sorted, and have
at most one element with any particular value.  I wrote a
library of routines to add, delete, merge, count, test, etc.
lists.  Most of the lists are short, so traversal time is low
and insertion into a sorted list is fast.  My implementation
has a list[] array and a link[] array, so I have lots of code
that looks like:

list_t p;
for(p = libertylist[group1]; p != EOL; p = link[p]){
	...  list[p] ...
}

If I were rewriting in C++ the code would be quite different of course :)

Bruce Wilcox used lists in Nemesis, but he stored them in small arrays
rather than
in a list/link structure.

David

At 09:51 PM 3/25/99 -0800, Philipp Garcia wrote:
>I have a few questions for all you Go programmers:
>
>Do you use bitmap or list type structures in "objects" (term used loosely)
>to represent strings, blocks, liberties lists, etc?
>
>I am wondering if board evaluation using linked-lists is faster than using
>bitmaps. Just by using bitwise operations (i.e.., OR, AND, XOR and NOT) on a
>bitmaps, it is relatively easy to implement the merging of two (or more)
>strings after being connected by stone; along with maintaining a bitmap of
>liberties. However, I have found that many of my algorithms have to count
>the number of bits set in the bitmap (i.e., in recalculating each remaining
>string's liberty count after an opponent's string is captured) or have to
>convert a bitmap into a list for some non-trivial operations. These types of
>operations generally take a fixed about of time to execute. However, the
>time to traverse a list is, instead, dependent on the size of the list. So
>it could be faster in many cases. Since I have to create lists and count
>bits so much, I'm thinking about scrapping my bitmap representations almost
>entirely. Is this a good move or should I stick to what I got? (I'm not
>particularly concerned about using bitmaps for pattern matching; I have a
>few ideas on how to quickly get a few hash values from a list-structure to
>efficiently prune a database search - but that's another topic).
>
>David, in Many Faces of Go, I remember you stating a long time ago that you
>used linked-lists rather than bitmaps. Is that still the case?
>
>Thanks in advance,
>
>Phil
>
>
>
>
>
>