Re: Treap instead of splaytree for GSequence

On 13 Feb 2007 03:46:11 +0100, Soeren Sandmann <sandmann daimi au dk> 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.


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