Re: Skip List for GLIB

[Xavier Claessens <xclaesse gmail com>]

Le jeudi 23 décembre 2010 à 11:53 +0100, Sebastian Dröge a écrit :
> On Wed, 2010-12-22 at 15:07 -0500, Eric Vander Weele wrote:
> > 
> > 
> > 2010/12/22 Sebastian Dröge <sebastian droege collabora co uk>
> >         On Wed, 2010-12-22 at 11:03 -0500, Eric Vander Weele wrote:
> >         > Hello,
> >         >
> >         >
> >         > Before I started working on this, I wanted to bounce the
> >         idea of
> >         > adding a skip list -- GSkipList.  It shouldn't be that more
> >         > complicated than the balanced binary tree implementation and
> >         the test
> >         > driver for a skip list would almost be the same as the the
> >         one for the
> >         > balanced binary tree.
> >         
> >         
> >         What would be the advantage over GSequence (which internally
> >         uses a
> >         balanced binary tree)? Would you implement a deterministic
> >         (which of the
> >         many variants?) or probabilistic skip list (would you expose
> >         the level
> >         selection probability to allow slower but less memory hungry
> >         skiplists?)?
> >         
> > 
> > Insertion/deletion/search could be done with amortized O(log n) time,
> > which is similar to GSequence if insertions are done using the
> > 'insert_sorted()' methods.  However, the advantage over GSequence is
> > that insertions are always sorted, there would be no 'prepend' or
> > 'append' methods and the space efficiency of skip lists is also an
> > advantage over GSequence and GTree.  
> 
> Right, a GSequence can be unsorted but then it doesn't really have any
> advantage over GList unless I'm missing something :)

This is not true. g_sequence_append() means "I know this element is
bigger than all others, so you can append it without wasting time on
comparaisons". This is useful for example when inserting elements in a
GSequence in an order you already know is sorted.

Regards,
Xavier Claessens