Re: Group sorting

[larsi@ifi.uio.no (Lars Magne Ingebrigtsen)]

dreschs@mpd.tandem.com (Sten Drescher) writes:

> LMI> (lambda (g1 g2)
> LMI>   (or (gnus-group-sort-by-unread g1 g2)
> LMI>       (and (not (gnus-group-sort-by-unread g2 g1))
> LMI> 	          (gnus-group-sort-by-level g1 g2))))
> 
> 	I don't know, because I don't understand the elisp - what is it
> doing?  Is it still sorting the entire list of groups between g1 and g2,
> or does that fragment just compare two groups?  If each
> gnus-group-sort-by-x sorts a list of groups, then no, it appears that it
> will be worse, as you are doing three sorts instead of two!

This lambda form would be given as an argument to the `sort' function,
so this is something that compares two groups.  The names of the
functions are misnomers; they should be called `gnus-group-unread-<'
and `gnus-group-level-<'.

> 	As it is now, two entire sorts are done with one key each -
> every group is sorted by level, then every group is sorted by
> unread. I'm proposing that one sort be done with two keys - every group
> is sorted by unread, then ONLY IF the unread counts are equal are the
> two groups being compared sorted by level. 

Yes; that's what the lambda form above does.  Just read it very
slowly.  :-)  

> This is a _significant_ difference in sort time, as only a small
> percentage of groups will have identical unread counts.

I have done no measurements.  With this scheme we would have an
uncompiled lambda form (with ~1.7 funcalls) that would be executed
O(n*log(n)) times.  Sorting twice (the normal way) would execute a
compiled function (with 0 funcalls) O(2*n*log(n)) times.  Anybody want
to benchmark it?

> This difference might be noticable with a small number of groups,
> but even with only about 2500 groups I can tell the difference
> between one and two sorts, and I'm dreading seeing even a single
> sort with the 14,000 groups my ISP carries.  Remember, the time for
> a bubble sort grows as the square of the number of sorted items.

Fortunately Emacs `sort' isn't a bubble sort.  (What is it, though?
Fastsort?) 

-- 
Home is where the cat is.