Oscar Lazzarino <oscar.lazzarino@xxxxxxxxx> 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@xxxxxxxxx http://mail.gnome.org/mailman/listinfo/gtk-list
