Re: Skip List for GLIB



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 :)

You would only get better space efficiency (without performance penalty)
if you use a probability of 0.25 per level though (IIRC). For something
like the intuitive 0.5 there's not really a difference... other than
that GSequence offers worst-case O(log n) lookups/insertions while your
skip list would only offer this high probability.

> I was thinking about implementing a probabilistic skip list where the
> level selection probability and max level would be exposed to allow
> for tuning for space/time trade-offs depending on the application.

IMHO (not being a GLib maintainer) this would only be useful in very
specific scenarios and wouldn't be something for a general purpose
library like GLib. But maybe others disagree :)

Attachment: signature.asc
Description: This is a digitally signed message part



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]