* Group sorting @ 1995-12-05 17:31 Sten Drescher 1995-12-06 5:05 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 9+ messages in thread From: Sten Drescher @ 1995-12-05 17:31 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-05 17:31 Group sorting Sten Drescher @ 1995-12-06 5:05 ` Lars Magne Ingebrigtsen 1995-12-08 17:32 ` Sten Drescher 0 siblings, 1 reply; 9+ messages in thread From: Lars Magne Ingebrigtsen @ 1995-12-06 5:05 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-06 5:05 ` Lars Magne Ingebrigtsen @ 1995-12-08 17:32 ` Sten Drescher 1995-12-10 15:16 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 9+ messages in thread From: Sten Drescher @ 1995-12-08 17:32 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-08 17:32 ` Sten Drescher @ 1995-12-10 15:16 ` Lars Magne Ingebrigtsen 1995-12-11 16:37 ` Sten Drescher 0 siblings, 1 reply; 9+ messages in thread From: Lars Magne Ingebrigtsen @ 1995-12-10 15:16 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-10 15:16 ` Lars Magne Ingebrigtsen @ 1995-12-11 16:37 ` Sten Drescher 1995-12-12 20:59 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 9+ messages in thread From: Sten Drescher @ 1995-12-11 16:37 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-11 16:37 ` Sten Drescher @ 1995-12-12 20:59 ` Lars Magne Ingebrigtsen 1995-12-12 22:33 ` Sten Drescher 0 siblings, 1 reply; 9+ messages in thread From: Lars Magne Ingebrigtsen @ 1995-12-12 20:59 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-12 20:59 ` Lars Magne Ingebrigtsen @ 1995-12-12 22:33 ` Sten Drescher 1995-12-13 17:30 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 9+ messages in thread From: Sten Drescher @ 1995-12-12 22:33 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-12 22:33 ` Sten Drescher @ 1995-12-13 17:30 ` Lars Magne Ingebrigtsen 1995-12-14 15:56 ` Hallvard B Furuseth 0 siblings, 1 reply; 9+ messages in thread From: Lars Magne Ingebrigtsen @ 1995-12-13 17:30 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Group sorting 1995-12-13 17:30 ` Lars Magne Ingebrigtsen @ 1995-12-14 15:56 ` Hallvard B Furuseth 0 siblings, 0 replies; 9+ messages in thread From: Hallvard B Furuseth @ 1995-12-14 15:56 UTC (permalink / raw) Cc: ding > 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~1995-12-14 15:56 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1995-12-05 17:31 Group sorting Sten Drescher 1995-12-06 5:05 ` Lars Magne Ingebrigtsen 1995-12-08 17:32 ` Sten Drescher 1995-12-10 15:16 ` Lars Magne Ingebrigtsen 1995-12-11 16:37 ` Sten Drescher 1995-12-12 20:59 ` Lars Magne Ingebrigtsen 1995-12-12 22:33 ` Sten Drescher 1995-12-13 17:30 ` Lars Magne Ingebrigtsen 1995-12-14 15:56 ` Hallvard B Furuseth
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).