From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/4379 Path: main.gmane.org!not-for-mail From: larsi@ifi.uio.no (Lars Magne Ingebrigtsen) Newsgroups: gmane.emacs.gnus.general Subject: Re: Group sorting Date: 13 Dec 1995 18:30:39 +0100 Organization: Dept. of Informatics, University of Oslo, Norway Sender: larsi@ifi.uio.no Message-ID: References: <55ka4b8lka.fsf@galil.austnsc.tandem.com> <557n07h36c.fsf@galil.austnsc.tandem.com> <55d99v7e0z.fsf@galil.austnsc.tandem.com> <55ivjlud3u.fsf@galil.austnsc.tandem.com> NNTP-Posting-Host: coloc-standby.netfonds.no X-Trace: main.gmane.org 1035145133 29387 80.91.224.250 (20 Oct 2002 20:18:53 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Sun, 20 Oct 2002 20:18:53 +0000 (UTC) Return-Path: ding-request@ifi.uio.no Original-Received: from ifi.uio.no (ifi.uio.no [129.240.64.2]) by miranova.com (8.6.11/8.6.9) with ESMTP id KAA16992 for ; Wed, 13 Dec 1995 10:21:33 -0800 Original-Received: from gymir.ifi.uio.no (4867@gymir.ifi.uio.no [129.240.80.2]) by ifi.uio.no with ESMTP (8.6.11/ifi2.4) id for ; Wed, 13 Dec 1995 18:30:40 +0100 Original-Received: (from larsi@localhost) by gymir.ifi.uio.no ; Wed, 13 Dec 1995 18:30:40 +0100 Original-To: ding@ifi.uio.no In-Reply-To: dreschs@mpd.tandem.com's message of 12 Dec 1995 16:33:09 -0600 Original-Lines: 47 Xref: main.gmane.org gmane.emacs.gnus.general:4379 X-Report-Spam: http://spam.gmane.org/gmane.emacs.gnus.general:4379 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.