Re: Skip List for GLIB
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 > > 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 ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: Skip List for GLIB
2010/12/23 Matthias Clasen > 2010/12/23 Sebastian Dröge : > > > > > 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 :) > > > > No, I think you pretty much nailed it. GLib is not a data structure > library. > > We don't generally add new data structures unless there's a specific > need for them somewhere in the GTK+ stack. If you are interested in a > wide variety of data structure variants with different speed/space > tradeoffs, there's other libraries out there, like libavl... > I agree with your (Sebastian and Matthias) points and appreciate your feedback. The more I think about it, skip list is a niche data structure. ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: Skip List for GLIB
2010/12/23 Sebastian Dröge : > > 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 :) > No, I think you pretty much nailed it. GLib is not a data structure library. We don't generally add new data structures unless there's a specific need for them somewhere in the GTK+ stack. If you are interested in a wide variety of data structure variants with different speed/space tradeoffs, there's other libraries out there, like libavl... ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: Skip List for GLIB
On Wed, 2010-12-22 at 15:07 -0500, Eric Vander Weele wrote: > > > 2010/12/22 Sebastian Dröge > 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
Re: Skip List for GLIB
2010/12/22 Sebastian Dröge > 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. 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. Using NULL as the skip list terminator makes implementing a multi-set skip list more natural and slightly more efficient, but a set skip list implementation can be done as well. ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
Re: Skip List for GLIB
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?)? 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
Re: Skip List for GLIB
Eric Vander Weele writes: > 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. How would the interface differ from a balanced binary tree implementation? What is the benefit to having both? (I just read this mailing list. I don't speak for the GTK+ developers in any way.) -- Ben Pfaff http://benpfaff.org ___ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
