[ioke-dev] Re: Data structure melee

["Kosta Welke" <kosta@fillibach.de>]

On Fri, 30 Jan 2009 14:15:50 +0100, Ola Bini <ola.bini@gmail.com> wrote:

> Kosta Welke wrote:

> > The big problem I see is that if we update a parent, all children need  
> > to be informed. This could be eased by also remembering where the node  
> > comes from:

> > Now we only need to update children if cells are inserted or deleted.  
> > When inserting into node n, we only need to update children whose first  
> > parent is not n.

> Sure, that was implicit in my description of the second approach. That's  
> the only way it could work. It shouldn't be necessary to have an if  
> statement there though. We can just use the same link, but a subclass of  
> Node to keep information about a link to the next mimic.

Sure thing: virtual function call instead of if statement. Was just  
pseudocode anyway.

Well, I doubt there is much place for improvement algorithmically.

As I already mentioned, another tweak is using different data structures  
for different cases: e.g. a simple array with O(n) lookup for few cells,  
the hashtable-to-linked-list above for many cells and a lot of changes,  
perfect hashing for cells that change _rarely_ (Base, maybe?). But my wild  
guess is thats old news for you.

Obviously, either lookups are "slow" (i.e. depth-first search), or  
insertations/deletions are. Any cool caching technique is easily defeated  
by the changing nature of the graph structure.

As you already knew that, could you specify what you ment by "Ideas,  
thoughts?". Were you simply looking for a data structure with better  
properties that you didnt come up with (anf I cant think of either)?

Cheers,
Kosta