Re: Treap instead of splaytree for GSequence

[Soeren Sandmann <sandmann daimi au dk>]

"Nikolai Weibull" <now bitwi se> writes:

> 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.

Well, yes, since any operation with worst case or expected time O(log n)
is trivally also amortized O(log n).

The difference is that treaps have expected time O(log n) on
individual operations, where splay trees only have an O(n) bound.

> > 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.

Splay trees are only faster in the case where 

- you are inserting in sorted order into a sorted list

- the comparison function is really slow

and even in that case they are not much faster than treaps. By
tweaking the benchmark a little (to insert in random order) the splay
implementation became much slower than the treap one. 


Soren