On 13 Feb 2007 03:46:11 +0100, Soeren Sandmann <[EMAIL PROTECTED]> wrote: > GSequence is currently implemented with a splaytree which, even though > it is a neat data structure, has some downsides: > > * They are only O(log n) in the amortized sense > > This means individual operations can take a long time. This is a > problem for interactive applications where predictable performance is > often more important than good average performance.
Well, treaps have amortized time O(lg n) for their operations as well. > The performance as reported by testtreemodel is slightly worse with > treaps than with with splaytrees. The reason for this is that > > - gtk_list_store_compare_func() is really slow, so what is getting > measured here is more than anything how many times that function > gets called. Well, if this is the case, then it does sound like a splay makes more sense for this kind of application. Still, treaps are cool. nikolai _______________________________________________ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list
