From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Daniel Colascione Newsgroups: gmane.emacs.devel Subject: Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) Date: Sat, 29 May 2010 20:49:13 -0400 Organization: Censorship Research Center Message-ID: <4C01B609.6070303@censorshipresearch.org> References: <4C018D79.7040409@censorshipresearch.org> <4C018FD3.1020305@censorshipresearch.org> <4C01AA28.6030002@censorshipresearch.org> <9718A5AD-7A74-470B-A32D-DA14266506A3@raeburn.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigA2EFDBB88A2CEA0F330AEAE6" X-Trace: dough.gmane.org 1275180576 14062 80.91.229.12 (30 May 2010 00:49:36 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 30 May 2010 00:49:36 +0000 (UTC) Cc: Emacs development discussions To: Ken Raeburn Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun May 30 02:49:35 2010 connect(): No such file or directory Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1OIWic-0002Ks-Pa for ged-emacs-devel@m.gmane.org; Sun, 30 May 2010 02:49:35 +0200 Original-Received: from localhost ([127.0.0.1]:38465 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OIWic-0008BS-3b for ged-emacs-devel@m.gmane.org; Sat, 29 May 2010 20:49:34 -0400 Original-Received: from [140.186.70.92] (port=42761 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OIWiV-00089a-Ov for emacs-devel@gnu.org; Sat, 29 May 2010 20:49:28 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OIWiU-000239-Pl for emacs-devel@gnu.org; Sat, 29 May 2010 20:49:27 -0400 Original-Received: from haystack.austinheap.com ([70.32.98.68]:40814 helo=haystacknetwork.com) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OIWiU-000230-Np for emacs-devel@gnu.org; Sat, 29 May 2010 20:49:26 -0400 User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.1.9) Gecko/20100317 Thunderbird/3.0.4 In-Reply-To: <9718A5AD-7A74-470B-A32D-DA14266506A3@raeburn.org> X-Enigmail-Version: 1.0.1 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. 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:125354 Archived-At: This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigA2EFDBB88A2CEA0F330AEAE6 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On 5/29/10 8:45 PM, Ken Raeburn wrote: > On May 29, 2010, at 19:58, Daniel Colascione wrote: >> We do this only for the anonymous-variable case, but it's still an >> improvement. >=20 > If it's only in the anonymous case, where (if I understand > correctly) > the value isn't accessible until the loop construct returns a value, wh= y > not keep it simple and build the list in reverse, doing an nreverse cal= l > at the end? It doesn't need to be "in order" in the intermediate states= =2E > Is it any faster to build the list in order? (Simply avoiding nreverse > obviously makes things a little faster, but are you doing more work eac= h > time around the loop to maintain and use the tail pointer?) It's only a little bit more work to use the tail pointer, and it saves having to traverse the entire list on return, which could be a lot of work for a large list. For small lists, it might be a tossup, but then the difference doesn't matter much in that case anyway. Also, other LOOP implementations use tail pointers. --------------enigA2EFDBB88A2CEA0F330AEAE6 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (Darwin) iEYEARECAAYFAkwBtgwACgkQ17c2LVA10VugNgCeIG0meslkCSzAqzgF/yVePbWV +O4AnjY0Hnag5t4i3xJQ0h3mrolkoTFg =VUk1 -----END PGP SIGNATURE----- --------------enigA2EFDBB88A2CEA0F330AEAE6--