Yes, 4 is very similar to doubly linked lists in memory size. I think it's a little faster. To save memory, I don't use pointers. I use 2-byte indexes into arrays.
David > -----Original Message----- > From: computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] On Behalf Of Isaac Deutsch > Sent: Saturday, July 11, 2009 9:46 AM > To: computer-go > Subject: Re: [computer-go] Keep lists of stones in a group? > > Isn't 4. similar to doubly linked lists? You have to keep almost as > many pointers as there are points on the board at most. How do you > effectively store the pointers to only use as few as possible? > > I don't see how 5) is good for removing groups. Are there other uses > for the bitmaps? > > Am 11.07.2009 um 18:27 schrieb Moi de Quoi: > > > On Sat, 2009-07-11 at 08:57 -0700, David Fotland wrote: > >> 4. Keep a singly linked list of stones for each group and keep an > >> additional pointer for each group to the last element of the list. > >> This is > >> what I do in Many Faces. > > > > 5) Use a bitmap. This costs a bit more memory (if one bitmap is > > allocated per stone), but may have a better locality of reference. > > Also, there are fewer corner cases wrt cyclic/ empty linked lists, > > etc. > > > > AvK > > > > _______________________________________________ > > computer-go mailing list > > computer-go@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/