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.
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 7:48 AM > To: computer-go > Subject: [computer-go] Keep lists of stones in a group? > > > Hello, > > I'm thinking about wether it's better to keep a list of stones for > each group in the board state or not. > > I'm keeping a linked list of liberties like Lukasz suggested and it is > useful in many cases, but the only case that access to all stones in a > group is handy is when removing it. I'm already keeping track of group > membership for each stone with union-find. This is needed for the > liberty management. > > There are 3 options I can think of: > 1. Keep a doubly linked list for each group. Takes about 1.5 KB ram > for 19x19. Stone insertion is O(1), merging is O(1). > 2. Keep a simple linked list. Takes about 700B ram. Stone insertion is > O(1), but merging is O(min(n,m)) where n,m are the sizes of the groups > being merged. > 3. Don't keep lists at all. No merging or insertion, takes no ram. > > In all 3 cases, removing a group takes O(n), n being the size of the > group. Option 3 might be a bit slower there because a stack has to be > used to perform DFS on the group, also option 3 takes additional > memory for the stack. > > Over all, which do you think is the fastest? All options seem to take > about the same amount of effort to maintain. > > Regards, > Isaac > > p.s. Sorry if this is a double post, I couldn't verify that the > message was sent to the mailing list the first time. > > _______________________________________________ > 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/
