Re: Treap instead of splaytree for GSequence

["Nikolai Weibull" <now bitwi se>]

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.

 nikolai