Re: Treap instead of splaytree for GSequence
- From: "Nikolai Weibull" <now bitwi se>
- To: "Soeren Sandmann" <sandmann daimi au dk>
- Cc: gtk-devel-list gnome org
- Subject: Re: Treap instead of splaytree for GSequence
- Date: Tue, 13 Feb 2007 10:16:10 +0100
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
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.
] [Thread Prev