[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Adding many elements to a list
From: |
Pascal J. Bourguignon |
Subject: |
Re: Adding many elements to a list |
Date: |
Fri, 18 Sep 2009 15:44:36 +0200 |
User-agent: |
Gnus/5.101 (Gnus v5.10.10) Emacs/22.2 (gnu/linux) |
Nordlöw <per.nordlow@gmail.com> 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__
- Adding many elements to a list, Nordlöw, 2009/09/18
- Re: Adding many elements to a list,
Pascal J. Bourguignon <=
- Re: Adding many elements to a list, David Kastrup, 2009/09/18
- Re: Adding many elements to a list, Pascal J. Bourguignon, 2009/09/19
- Re: Adding many elements to a list, David Kastrup, 2009/09/18
- Re: Adding many elements to a list, Thierry Volpiatto, 2009/09/18
- Re: Adding many elements to a list, Pascal J. Bourguignon, 2009/09/19
- Re: Adding many elements to a list, Andreas Politz, 2009/09/19
- Re: Adding many elements to a list, David Kastrup, 2009/09/22
- Re: Adding many elements to a list, Pascal J. Bourguignon, 2009/09/22
- Re: Adding many elements to a list, David Kastrup, 2009/09/22
- Re: Adding many elements to a list, Pascal J. Bourguignon, 2009/09/22