Group sorting

Group sorting

[Sten Drescher]

	From the Info pages:

Info> The `C-c C-s' (`gnus-group-srot-groups')[sic] command sorts the
Info> group buffer according to the function(s) given by the
Info> `gnus-group-sort-function' variable.  Available sorting functions
Info> include: 

[...]

Info> There are also a number of commands for sorting directly according
Info> to some sorting criteria: 

[...]

Info> When given a prefix, all these commands will sort in reverse
Info> order.

	Is it possible to reverse the sort in gnus-group-sort-function?

-- 
#include <disclaimer.h>				/* Sten Drescher */
To get my PGP public key, send me email with your public key and
	Subject: PGP key exchange
Key fingerprint =  90 5F 1D FD A6 7C 84 5E  A9 D3 90 16 B2 44 C4 F3

Re: Group sorting

[Lars Magne Ingebrigtsen]

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

> Info> When given a prefix, all these commands will sort in reverse
> Info> order.
> 
> 	Is it possible to reverse the sort in gnus-group-sort-function?

Yes.  Give the commands a prefix.

-- 
Home is where the cat is.

Re: Group sorting

[Sten Drescher]

larsi@ifi.uio.no (Lars Magne Ingebrigtsen) said:

LMI> dreschs@mpd.tandem.com (Sten Drescher) writes:
Info> When given a prefix, all these commands will sort in reverse
Info> order.
>>  Is it possible to reverse the sort in gnus-group-sort-function?

LMI> Yes.  Give the commands a prefix.

	I want to sort decending by unread, and ascending by level, so
that doesn't do it.  Of course, I also want it to take a reasonable
amount of time, and putting multiple 'keys' in gnus-group-sort-function
causes a linear increase in the time required, so I'm doing without the
level sort. ;(  Is making a better sort algorithm (passing a list of keys
to compare rather than individual sorts on each key) on the to-do list?

-- 
#include <disclaimer.h>				/* Sten Drescher */
To get my PGP public key, send me email with your public key and
	Subject: PGP key exchange
Key fingerprint =  90 5F 1D FD A6 7C 84 5E  A9 D3 90 16 B2 44 C4 F3

Re: Group sorting

[Lars Magne Ingebrigtsen]

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

> 	I want to sort decending by unread, and ascending by level, so
> that doesn't do it.  

No, that's right...  I think you'll have to write your own comparison
functions to do that:

(defun sten-sort (info1 info2)
  (let ((n1 (car (gnus-gethash (gnus-info-group info1) gnus-newsrc-hashtb)))
	(n2 (car (gnus-gethash (gnus-info-group info2) gnus-newsrc-hashtb))))
    (or (< (gnus-info-level info1) (gnus-info-level info2))
	(and (= (gnus-info-level info1) (gnus-info-level info2))
	     (< (or (and (numberp n1) n1) 0)
		(or (and (numberp n2) n2) 0))))))

Or something like that.  (Would it be the other way around, perhaps?)

> Of course, I also want it to take a reasonable
> amount of time, and putting multiple 'keys' in gnus-group-sort-function
> causes a linear increase in the time required, so I'm doing without the
> level sort. ;(  Is making a better sort algorithm (passing a list of keys
> to compare rather than individual sorts on each key) on the to-do list?

Nope.  Could you illustrate what you had in mind?

-- 
Home is where the cat is.

Re: Group sorting

[Sten Drescher]

larsi@ifi.uio.no (Lars Magne Ingebrigtsen) said:

>> Of course, I also want it to take a reasonable amount of time, and
>> putting multiple 'keys' in gnus-group-sort-function causes a linear
>> increase in the time required, so I'm doing without the level
>> sort. ;( Is making a better sort algorithm (passing a list of keys to
>> compare rather than individual sorts on each key) on the to-do list?

LMI> Nope.  Could you illustrate what you had in mind?

	OK, right now, to get close to what I want, I'd set:

(setq gnus-group-sort-function '(gnus-group-sort-by-level
                                gnus-group-sort-by-unread))

	This would first do a complete sorting by level, then a complete
sorting by unread - 2 complete sorts.  I'd want it to work in a single
sort - the sort would compare the unread keys, and _only_ if they
matched, compare the level keys.  I don't know enough elisp to know how
(or if) this could be implemented.

-- 
#include <disclaimer.h>				/* Sten Drescher */
To get my PGP public key, send me email with your public key and
	Subject: PGP key exchange
Key fingerprint =  90 5F 1D FD A6 7C 84 5E  A9 D3 90 16 B2 44 C4 F3

Re: Group sorting

[Lars Magne Ingebrigtsen]

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

> (setq gnus-group-sort-function '(gnus-group-sort-by-level
>                                 gnus-group-sort-by-unread))
> 
> 	This would first do a complete sorting by level, then a complete
> sorting by unread - 2 complete sorts.  I'd want it to work in a single
> sort - the sort would compare the unread keys, and _only_ if they
> matched, compare the level keys. 

Ok, that would be workable.  Gnus could transmogrify that list to

(lambda (g1 g2)
  (or (gnus-group-sort-by-unread g1 g2)
      (and (not (gnus-group-sort-by-unread g2 g1))
	   (gnus-group-sort-by-level g1 g2))))

and give that as the predicate to sort.  Won't this give you the same
results as first using `gnus-group-sort-by-level' as a predicate and
then `gnus-group-sort-by-unread' as a predicate for sort?

I have no idea whether it will be faster, though...

(`gnus-group-sort-by-level' should really be called
`gnus-group-level-less' or something since it is a `less' function and
not an actual sorting function...)

-- 
Home is where the cat is.

Re: Group sorting

[Sten Drescher]

larsi@ifi.uio.no (Lars Magne Ingebrigtsen) said:

LMI> dreschs@mpd.tandem.com (Sten Drescher) writes:
>> (setq gnus-group-sort-function '(gnus-group-sort-by-level
>> gnus-group-sort-by-unread))
>> 
>> This would first do a complete sorting by level, then a complete
>> sorting by unread - 2 complete sorts.  I'd want it to work in a
>> single sort - the sort would compare the unread keys, and _only_ if
>> they matched, compare the level keys.

LMI> Ok, that would be workable.  Gnus could transmogrify that list to

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))))

LMI> and give that as the predicate to sort.  Won't this give you the
LMI> same results as first using `gnus-group-sort-by-level' as a
LMI> predicate and then `gnus-group-sort-by-unread' as a predicate for
LMI> sort?

LMI> I have no idea whether it will be faster, though...

	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!

	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.  This is a _significant_
difference in sort time, as only a small percentage of groups will have
identical unread counts.  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.
However,

LMI> (`gnus-group-sort-by-level' should really be called
LMI> `gnus-group-level-less' or something since it is a `less' function
LMI> and not an actual sorting function...)

LMI> -- Home is where the cat is.



-- 
#include <disclaimer.h>				/* Sten Drescher */
To get my PGP public key, send me email with your public key and
	Subject: PGP key exchange
Key fingerprint =  90 5F 1D FD A6 7C 84 5E  A9 D3 90 16 B2 44 C4 F3

Re: Group sorting

[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.

Re: Group sorting

[Hallvard B Furuseth]

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

Naive quicksort, splitting its argument on the middle.  See src/fns.c.


Hallvard