From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: pjb@informatimago.com (Pascal J. Bourguignon) Newsgroups: gmane.emacs.help Subject: Re: Adding many elements to a list Date: Fri, 18 Sep 2009 15:44:36 +0200 Organization: Anevia SAS Message-ID: <7chbv0fjuj.fsf@anevia.com> References: <979e809f-0b95-46bf-afa4-1a25cda5bae0@j9g2000vbp.googlegroups.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1253284889 11778 80.91.229.12 (18 Sep 2009 14:41:29 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 18 Sep 2009 14:41:29 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Fri Sep 18 16:41:22 2009 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1MoeeI-0000f0-AX for geh-help-gnu-emacs@m.gmane.org; Fri, 18 Sep 2009 16:41:22 +0200 Original-Received: from localhost ([127.0.0.1]:54238 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MoeeH-00015f-Av for geh-help-gnu-emacs@m.gmane.org; Fri, 18 Sep 2009 10:41:21 -0400 Original-Path: news.stanford.edu!usenet.stanford.edu!news.tele.dk!news.tele.dk!small.news.tele.dk!proxad.net!feeder1-2.proxad.net!cleanfeed2-b.proxad.net!nnrp17-1.free.fr!not-for-mail Original-Newsgroups: gnu.emacs.help Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en X-Disabled: X-No-Archive: no User-Agent: Gnus/5.101 (Gnus v5.10.10) Emacs/22.2 (gnu/linux) Cancel-Lock: sha1:CaCkeWtkRzSHaGgt/RVJL5S8ciI= Original-Lines: 99 Original-NNTP-Posting-Date: 18 Sep 2009 15:44:36 MEST Original-NNTP-Posting-Host: 88.170.236.224 Original-X-Trace: 1253281476 news-1.free.fr 442 88.170.236.224:53037 Original-X-Complaints-To: abuse@proxad.net Original-Xref: news.stanford.edu gnu.emacs.help:173150 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:68273 Archived-At: Nordlöw writes: > What is the most efficient way of performing lots of successive > appends of elements to the same list? > > If we start with defining the list > > (setq l '(a b)) > > then the Emacs manual says that we can use > > (nconc l '(c d))) No, that's not possible. You mustn't modify a literal data. See what happens if you do it: (defun f () (setq l '(a b)) (nconc l '(c d))) (list (f) (f)) --> (#1=(a b . #2=(c d . #2#)) #1#) A third call to (f) will result in an infinite loop. What you should do, is to build a new list everytime you want to modify it with nconc. You should also try to avoid setq and rather use let: (defun g () (let ((l (list 'a 'b))) (nconc l (list 'c 'd)) l)) (list (g) (g) (g)) --> ((a b c d) (a b c d) (a b c d)) > I have noticed that this works in all cases except when l is nil. Of course. As I wrote above, you mustn't modify a literal data. And in the case of nil, you just cannot modify it, since it's a constant. > To make this case work aswell we need to do use > > (setq l (nconc l '(c d)))) > > > Or can we use setcar or setcdr in a more clever way? No. setcar and setcdr take cons cells, not symbols. nil is a symbol. > Reflections? In general in Lisp, it's more efficient to build the lists from the end to the head: push on the head instead. If the final result is in the reversed order, you can always reverse it. (defun h () (let ((l (list 'c 'd))) (append '(a b) l))) (list (h) (h) (h)) --> ((a b c d) (a b c d) (a b c d)) Notice that we used a literal list as argument to append. This is possible because append copies all its arguments but the last. And since append doesn't make a copy of the last argument, we provided it a new list so it may be modified: (list (let ((l (h))) (nconc l (list 3 4)) l) (h) (h)) --> ((a b c d 3 4) (a b c d) (a b c d)) (defun i () (let ((l '(c d))) (append '(a b) l))) (list (i) (i) (i)) --> ((a b . #1=(c d)) (a b . #1#) (a b . #1#)) (list (let ((l (i))) (nconc l (list 3 4)) l) (i) (i)) --> ((a b . #1=(c d 3 4 3 4)) (a b . #1#) (a b . #1#)) So better use (require 'cl) (push new-item list) or (cons new-item list) or (append (list new-items...) list) and possibly (reverse the-result), or (nreverse the-result) if you took care of producing a list that doesn't share tail (ie. like g or h, but not like f or i), than (nconc list (list new-items...)) or (append list (list new-items...)). Using these later forms inside a loop will kill your time complexity. -- __Pascal Bourguignon__