On Wed, 2010-12-22 at 15:07 -0500, Eric Vander Weele wrote:
2010/12/22 Sebastian Dröge sebastian.dro...@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 :)
signature.asc
Description: This is a digitally signed message part
___
gtk-devel-list mailing list
gtk-devel-list@gnome.org
http://mail.gnome.org/mailman/listinfo/gtk-devel-list
