Re: Bitmaps vs Lists

["P.J.Leonard" <P.J.Leonard@xxxxxxxxxx>]

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).
> used linked-lists rather than bitmaps. Is that still the case?

 In pubgo+ we have both. Strings are represented as linked lists.
However,
representing larger areas is probably best done using bit maps.
Expanding
a bit map by one layer is very fast using shift and bitwise and
operations. I use use this
for calculating territory. I have a common absract Area base class for
both
point collections (Lists) and bit maps. If you do this you can write a
lot
of code that does not care if it is dealing with bit maps or lists. 

 IIRC An absract area provides a virtual bool contain(POint p)=0
function and a 
virtual PointIterator *createIterator()=0; function. A PointIterator is
again absract.

 This scheme was one of the more successful uses of OO in pubgo !!!!

-- 
 Cheers Paul.                                        

  Tel: +44 1225 826108
  Fax: +44 1225 826305
snail: P.J.Leonard
       Applied Electromagnetic Research Centre
       Bath University,
       BATH, UK   BA2 7AY