Oscar Lazzarino <oscar.lazzarino@i-m3...> writes:

> So appending n rows costs n*log(n), instead of n. Could be worse, but
> could also be better, considering that the g_sequence has a
> g_sequence_append method...

g_sequence_append() is Theta(n*log(n)) too.

Also, GSequence is not actually a splay tree anymore, it is a treap
(http://en.wikipedia.org/wiki/Treap).

If GSequence actually *were* a splay tree, and the GtkListStore were
unsorted, then append() would be O(1) due to the move-to-root nature of
splay trees. In practice, this log n factor disappears in the noise, and
the horrible (CPU-)cache behavior of splay trees make them much slower
than treaps. See:

    http://mail.gnome.org/archives/gtk-devel-list/2007-February/msg00048.html

Soren

> Incidentally, I found that calling calling gtk_list_store_prepend with
> rows in reverse order is faster than using gtk_list_store_append

The difference is almost certainly very tiny, but _prepend() does avoid
one call to g_sequence_get_length().


Soren
_______________________________________________
gtk-list mailing list
gtk-list@gnom...
http://mail.gnome.org/mailman/listinfo/gtk-list