From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Miles Bader Newsgroups: gmane.emacs.devel Subject: Re: cl.el sort* efficiency Date: Sun, 24 Dec 2006 11:08:53 +0900 Message-ID: <87hcvmdozu.fsf@catnip.gol.com> References: <87ac1foi1f.fsf@zip.com.au> <87ejqq6rij.fsf@zip.com.au> Reply-To: Miles Bader NNTP-Posting-Host: dough.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1166926170 2393 80.91.229.10 (24 Dec 2006 02:09:30 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sun, 24 Dec 2006 02:09:30 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Dec 24 03:09:28 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 1GyInm-0002Qo-6C for ged-emacs-devel@m.gmane.org; Sun, 24 Dec 2006 03:09:26 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1GyInl-00084a-KM for ged-emacs-devel@m.gmane.org; Sat, 23 Dec 2006 21:09:25 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1GyInV-00082D-SS for emacs-devel@gnu.org; Sat, 23 Dec 2006 21:09:09 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1GyInT-000804-WA for emacs-devel@gnu.org; Sat, 23 Dec 2006 21:09:08 -0500 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1GyInT-0007zo-3x for emacs-devel@gnu.org; Sat, 23 Dec 2006 21:09:07 -0500 Original-Received: from [203.216.5.72] (helo=smtp02.dentaku.gol.com) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA:32) (Exim 4.52) id 1GyInR-0004ht-He; Sat, 23 Dec 2006 21:09:05 -0500 Original-Received: from 203-216-98-080.dsl.gol.ne.jp ([203.216.98.80] helo=catnip.gol.com) by smtp02.dentaku.gol.com with esmtpa (Dentaku) id 1GyInM-0003UB-Cs; Sun, 24 Dec 2006 11:09:00 +0900 Original-Received: by catnip.gol.com (Postfix, from userid 1000) id 68E1A2F40; Sun, 24 Dec 2006 11:08:53 +0900 (JST) Original-To: Kevin Ryde System-Type: i686-pc-linux-gnu In-Reply-To: <87ejqq6rij.fsf@zip.com.au> (Kevin Ryde's message of "Sun\, 24 Dec 2006 11\:56\:20 +1100") Original-Lines: 17 X-Abuse-Complaints: abuse@gol.com 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:64197 Archived-At: Kevin Ryde writes: > 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? I don't know how representative I am, but it's pretty obvious to me that adding something like :key to sort might call the given function multiple times. Certainly the alternative of allocating storage to keep around all retrieved key values is pretty heavyweight and in many cases not an optimization at all, so it's not something I would expect an implementation to do. -Miles -- `...the Soviet Union was sliding in to an economic collapse so comprehensive that in the end its factories produced not goods but bads: finished products less valuable than the raw materials they were made from.' [The Economist]