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