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: O(N^2) behavior in LOOP Date: Sat, 29 May 2010 17:56:09 -0400 Organization: Censorship Research Center Message-ID: <4C018D79.7040409@censorshipresearch.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigC838B0072B2940C413AC6487" X-Trace: dough.gmane.org 1275170195 23345 80.91.229.12 (29 May 2010 21:56:35 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sat, 29 May 2010 21:56:35 +0000 (UTC) To: Emacs development discussions Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat May 29 23:56:34 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 1OIU1B-0002lZ-Oq for ged-emacs-devel@m.gmane.org; Sat, 29 May 2010 23:56:34 +0200 Original-Received: from localhost ([127.0.0.1]:48691 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OIU1B-0006fs-Af for ged-emacs-devel@m.gmane.org; Sat, 29 May 2010 17:56:33 -0400 Original-Received: from [140.186.70.92] (port=39723 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OIU15-0006eG-DC for emacs-devel@gnu.org; Sat, 29 May 2010 17:56:28 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OIU14-0004md-EI for emacs-devel@gnu.org; Sat, 29 May 2010 17:56:27 -0400 Original-Received: from haystack.austinheap.com ([70.32.98.68]:43903 helo=haystacknetwork.com) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OIU14-0004mR-CT for emacs-devel@gnu.org; Sat, 29 May 2010 17:56: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 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:125347 Archived-At: This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigC838B0072B2940C413AC6487 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Erm, what's going on here? (loop for x in '(1 2 3) collect x into foo) Expands into (cl-block-wrapper (catch '--cl-block-nil-- (let* ((--cl-var-- '(1 2 3)) (x nil) (foo nil)) (while (consp --cl-var--) (setq x (car --cl-var--)) (setq foo (nconc foo (list x))) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ WTF? (setq --cl-var-- (cdr --cl-var--))) nil))) What is going on with the indicated line? That's O(N^2) because nconc has to traverse the entire 'foo' list each time a value is appended. Without the 'into' clause, loop uses push and nreverse, which, while still suboptimal, is at least linear. Before I go fix the loop macro, is there a _reason_ for the nconc silline= ss? --------------enigC838B0072B2940C413AC6487 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) iEYEARECAAYFAkwBjX0ACgkQ17c2LVA10VtGJACg0uYUQRKDEb440Jx+j0H97j0F wEQAnAhlNqV5et3HUmZgpfpPpr1u340u =EQNw -----END PGP SIGNATURE----- --------------enigC838B0072B2940C413AC6487--