Re: A tale of waiting

[Soeren Sandmann <sandmann daimi au dk>]

Matthias Clasen <matthias clasen gmail com> writes:

> > Next I implemented sorting. Because I use an array, I can use qsort(),
> > which is fast. I had thought about switching to GSequence to get ever
> > closer to GtkListStore, but I did not do that, and one of the reasons
> > is that GSequence uses insertion sort, which is quite slow.
> 
> Not sure why you keep repeating this, it is not true. GSequence is
> backed by a balanced tree, so sorting by insertion gives you O(n log
> n), so at least asymptotically,
> it is fine. The implementation may of course still be slower than
> qsort().

GSequence is indeed implemented with a randomized, balanced binary
tree (a treap[1] to be specific), so sorting is expected O(n log n).
While sorting a linked data structure is going to be slower than
qsort() on an array, 1 second for 40,000 elements sounds wrong,
so I'd be interested in seeing the benchmark.


Thanks,
Soren

[1] http://en.wikipedia.org/wiki/Treap