From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Juanma Barranquero" Newsgroups: gmane.emacs.devel Subject: Re: cl.el sort* efficiency Date: Sat, 23 Dec 2006 01:29:23 +0100 Message-ID: References: <87ac1foi1f.fsf@zip.com.au> NNTP-Posting-Host: dough.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: sea.gmane.org 1166833784 32358 80.91.229.10 (23 Dec 2006 00:29:44 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sat, 23 Dec 2006 00:29:44 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Dec 23 01:29:43 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 1Gxulf-0001Fx-Ac for ged-emacs-devel@m.gmane.org; Sat, 23 Dec 2006 01:29:39 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Gxule-0003Be-R4 for ged-emacs-devel@m.gmane.org; Fri, 22 Dec 2006 19:29:38 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1GxulS-00038A-L2 for emacs-devel@gnu.org; Fri, 22 Dec 2006 19:29:26 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1GxulQ-00034S-RN for emacs-devel@gnu.org; Fri, 22 Dec 2006 19:29:26 -0500 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1GxulQ-00034B-MA for emacs-devel@gnu.org; Fri, 22 Dec 2006 19:29:24 -0500 Original-Received: from [64.233.182.185] (helo=nf-out-0910.google.com) by monty-python.gnu.org with esmtp (Exim 4.52) id 1GxulQ-0001oW-9p for emacs-devel@gnu.org; Fri, 22 Dec 2006 19:29:24 -0500 Original-Received: by nf-out-0910.google.com with SMTP id d4so3549321nfe for ; Fri, 22 Dec 2006 16:29:23 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=mqUsM5qVtrLF+/sXREMmeBYyDe2VhGXsqIemNbFcGbCVwxMcCWFahMte3ilDuzKD0fzUvW/+Lj2aW/L36qjcDYsfOW7SS8Xrmp7z7HuHLk7PKBc784tqpGKCvgzC/aOgyZT+JPoRusSCwabg1rSfNgd76ItKzb3a0DoIZpbRKYI= Original-Received: by 10.82.190.2 with SMTP id n2mr388371buf.1166833763137; Fri, 22 Dec 2006 16:29:23 -0800 (PST) Original-Received: by 10.82.147.2 with HTTP; Fri, 22 Dec 2006 16:29:23 -0800 (PST) Original-To: "Kevin Ryde" In-Reply-To: <87ac1foi1f.fsf@zip.com.au> Content-Disposition: inline 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:64142 Archived-At: On 12/22/06, Kevin Ryde wrote: > I noticed that cl sort* function calls the given :key function within > every comparison, which is not good if key extraction is a big slow > calculation. [...] > The code below is an idea to build key results in an alist and sort > that. You're implementing a Schwartzian Transform (http://en.wikipedia.org/wiki/Schwartzian_transform) inside sort*, which is kinda odd. 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. 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... Perhaps you could encapsulate your ST in a function and use it as a wrapper for sort*. /L/e/k/t/u