From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Kevin Ryde Newsgroups: gmane.emacs.devel Subject: Re: cl.el sort* efficiency Date: Sun, 24 Dec 2006 11:56:20 +1100 Message-ID: <87ejqq6rij.fsf@zip.com.au> References: <87ac1foi1f.fsf@zip.com.au> NNTP-Posting-Host: dough.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: sea.gmane.org 1166921807 27161 80.91.229.10 (24 Dec 2006 00:56:47 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sun, 24 Dec 2006 00:56:47 +0000 (UTC) Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Dec 24 01:56:45 2006 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by dough.gmane.org with esmtp (Exim 4.50) id 1GyHfQ-0004rE-71 for ged-emacs-devel@m.gmane.org; Sun, 24 Dec 2006 01:56:44 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1GyHfP-00047j-MR for ged-emacs-devel@m.gmane.org; Sat, 23 Dec 2006 19:56:43 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1GyHf9-000437-7B for emacs-devel@gnu.org; Sat, 23 Dec 2006 19:56:27 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1GyHf8-00040R-6k for emacs-devel@gnu.org; Sat, 23 Dec 2006 19:56:26 -0500 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1GyHf7-000401-TN for emacs-devel@gnu.org; Sat, 23 Dec 2006 19:56:25 -0500 Original-Received: from [61.8.2.215] (helo=mailout1.pacific.net.au) by monty-python.gnu.org with esmtp (Exim 4.52) id 1GyHf6-00006Q-T8 for emacs-devel@gnu.org; Sat, 23 Dec 2006 19:56:25 -0500 Original-Received: from mailproxy2.pacific.net.au (mailproxy2.pacific.net.au [61.8.2.163]) by mailout1.pacific.net.au (Postfix) with ESMTP id 107C432833C for ; Sun, 24 Dec 2006 11:56:21 +1100 (EST) Original-Received: from localhost (ppp2F33.dyn.pacific.net.au [61.8.47.51]) by mailproxy2.pacific.net.au (Postfix) with ESMTP id 3289E27416 for ; Sun, 24 Dec 2006 11:56:20 +1100 (EST) Original-Received: from gg by localhost with local (Exim 4.63) (envelope-from ) id 1GyHf2-0001xB-MQ for emacs-devel@gnu.org; Sun, 24 Dec 2006 11:56:20 +1100 Original-To: emacs-devel@gnu.org In-Reply-To: (Juanma Barranquero's message of "Sat, 23 Dec 2006 01:29:23 +0100") User-Agent: Gnus/5.110006 (No Gnus v0.6) Emacs/21.4 (gnu/linux) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:64183 Archived-At: --=-=-= "Juanma Barranquero" writes: > > You're implementing a Schwartzian Transform > (http://en.wikipedia.org/wiki/Schwartzian_transform) inside sort*, > which is kinda odd. The concept would pre-date 1994, wouldn't it? (Not that this is the place for questions of academic priority :-) > IMHO is the responsibility of the user of sort* to know whether > comparisons are going to be expensive and preprocess the data to help > in the comparison. A key func as data accessor seemed to me a reasonably natural way to express that, but maybe that's just me. > You're doing an optimization at the wrong level: > perhaps I'm using it with so light a comparison function that your > method makes it more expensive... I see the common lisp spec specifically doesn't say how much or little the key is used. Dunno what you get from implementations in practice. Is there a CL expert in the house? In any case Richard advises not doing anything to emacs at this time, but I would propose a sentence for the manual, just to describe what's current. 2006-12-24 Kevin Ryde * cl.texi (Sorting Sequences): In sort*, add a little cautionary note about the key procedure being used heavily. --=-=-= Content-Type: text/x-diff Content-Disposition: attachment; filename=cl.texi.sort-key.diff Index: cl.texi =================================================================== RCS file: /sources/emacs/emacs/man/cl.texi,v retrieving revision 1.30 diff -u -c -r1.30 cl.texi cvs diff: conflicting specifications of output style *** cl.texi 22 Dec 2006 23:27:28 -0000 1.30 --- cl.texi 24 Dec 2006 00:43:47 -0000 *************** *** 4092,4098 **** @noindent sorts @var{data}, a sequence of strings, into increasing alphabetical order without regard to case. A @code{:key} function of @code{car} ! would be useful for sorting association lists. The @code{sort*} function is destructive; it sorts lists by actually rearranging the @code{cdr} pointers in suitable fashion. --- 4092,4100 ---- @noindent sorts @var{data}, a sequence of strings, into increasing alphabetical order without regard to case. A @code{:key} function of @code{car} ! would be useful for sorting association lists. It should only be a ! simple accessor though, it's used heavily in the current ! implementation. The @code{sort*} function is destructive; it sorts lists by actually rearranging the @code{cdr} pointers in suitable fashion. --=-=-= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Emacs-devel mailing list Emacs-devel@gnu.org http://lists.gnu.org/mailman/listinfo/emacs-devel --=-=-=--