Adding many elements to a list

Adding many elements to a list

[Nordlöw]

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)))

I have noticed that this works in all cases except when l is nil.
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?

Reflections?
Per Nordlöw

Re: Adding many elements to a list

[Pascal J. Bourguignon]

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__

Re: Adding many elements to a list

[David Kastrup]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> So better use (require 'cl) (push new-item list)
>    or (cons new-item list)
>    or (append (list new-items...) list)

(require 'cl) is quite unnecessary for all of the mentioned
alternatives.

-- 
David Kastrup

Re: Adding many elements to a list

[Pascal J. Bourguignon]

David Kastrup <dak@gnu.org> writes:

> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>
>> So better use (require 'cl) (push new-item list)
>>    or (cons new-item list)
>>    or (append (list new-items...) list)
>
> (require 'cl) is quite unnecessary for all of the mentioned
> alternatives.

Not on emacs version < 23.

-- 
__Pascal Bourguignon__

Re: Adding many elements to a list

[David Kastrup]

pjb@anevia.com (Pascal J. Bourguignon) writes:

> David Kastrup <dak@gnu.org> writes:
>
>> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>>
>>> So better use (require 'cl) (push new-item list)
>>>    or (cons new-item list)
>>>    or (append (list new-items...) list)
>>
>> (require 'cl) is quite unnecessary for all of the mentioned
>> alternatives.
>
> Not on emacs version < 23.

Nonsense.  push&pop were officially announced in Emacs 21.1.  I may be
mistaken, but I think they have been there even earlier.

And the other options certainly were there from the earliest versions of
GNU Emacs.

-- 
David Kastrup

Re: Adding many elements to a list

[Pascal J. Bourguignon]

David Kastrup <dak@gnu.org> writes:

> pjb@anevia.com (Pascal J. Bourguignon) writes:
>
>> David Kastrup <dak@gnu.org> writes:
>>
>>> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>>>
>>>> So better use (require 'cl) (push new-item list)
>>>>    or (cons new-item list)
>>>>    or (append (list new-items...) list)
>>>
>>> (require 'cl) is quite unnecessary for all of the mentioned
>>> alternatives.
>>
>> Not on emacs version < 23.
>
> Nonsense.  push&pop were officially announced in Emacs 21.1.  I may be
> mistaken, but I think they have been there even earlier.
>
> And the other options certainly were there from the earliest versions of
> GNU Emacs.


C-h f push RET
push is a Lisp macro in `cl.el'.
(push x place)

Insert x at the head of the list stored in place.
Analogous to (setf place (cons x place)), though more careful about
evaluating each argument only once and in the right order.  place may
be a symbol, or any generalized variable allowed by `setf'.

[back]

M-x emacs-version RET
GNU Emacs 22.2.1 (x86_64-unknown-linux-gnu, X toolkit) of 2008-08-21 on simias


-- 
__Pascal Bourguignon__

Re: Adding many elements to a list

[Andreas Politz]

pjb@anevia.com (Pascal J. Bourguignon) writes:

>
>
> C-h f push RET
> push is a Lisp macro in `cl.el'.
> (push x place)
>

It's a name-conflict.

$ emacs22 -q

,----[ push ]
| push is a Lisp macro in `subr.el'.
| (push newelt listname)
| 
| Add newelt to the list stored in the symbol listname.
| This is equivalent to (setq listname (cons newelt listname)).
| listname must be a symbol.
`----

-ap

Re: Adding many elements to a list

[David Kastrup]

pjb@anevia.com (Pascal J. Bourguignon) writes:

> David Kastrup <dak@gnu.org> writes:
>
>> pjb@anevia.com (Pascal J. Bourguignon) writes:
>>
>>> David Kastrup <dak@gnu.org> writes:
>>>
>>>> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>>>>
>>>>> So better use (require 'cl) (push new-item list)
>>>>>    or (cons new-item list)
>>>>>    or (append (list new-items...) list)
>>>>
>>>> (require 'cl) is quite unnecessary for all of the mentioned
>>>> alternatives.
>>>
>>> Not on emacs version < 23.
>>
>> Nonsense.  push&pop were officially announced in Emacs 21.1.  I may be
>> mistaken, but I think they have been there even earlier.
>>
>> And the other options certainly were there from the earliest versions of
>> GNU Emacs.
>
> C-h f push RET
> push is a Lisp macro in `cl.el'.
> (push x place)
>
> Insert x at the head of the list stored in place.
> Analogous to (setf place (cons x place)), though more careful about
> evaluating each argument only once and in the right order.  place may
> be a symbol, or any generalized variable allowed by `setf'.
>
> [back]
>
> M-x emacs-version RET
> GNU Emacs 22.2.1 (x86_64-unknown-linux-gnu, X toolkit) of 2008-08-21 on simias

Try emacs -Q.  Just because you choose to load some library overloading
the default operators does not mean that other people should do the same
when Emacs will provide those operators by default, with better
performance.

-- 
David Kastrup

Re: Adding many elements to a list

[Pascal J. Bourguignon]

David Kastrup <dak@gnu.org> writes:

> pjb@anevia.com (Pascal J. Bourguignon) writes:
>
>> David Kastrup <dak@gnu.org> writes:
>>
>>> pjb@anevia.com (Pascal J. Bourguignon) writes:
>>>
>>>> David Kastrup <dak@gnu.org> writes:
>>>>
>>>>> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>>>>>
>>>>>> So better use (require 'cl) (push new-item list)
>>>>>>    or (cons new-item list)
>>>>>>    or (append (list new-items...) list)
>>>>>
>>>>> (require 'cl) is quite unnecessary for all of the mentioned
>>>>> alternatives.
>>>>
>>>> Not on emacs version < 23.
>>>
>>> Nonsense.  push&pop were officially announced in Emacs 21.1.  I may be
>>> mistaken, but I think they have been there even earlier.
>>>
>>> And the other options certainly were there from the earliest versions of
>>> GNU Emacs.
>>
>> C-h f push RET
>> push is a Lisp macro in `cl.el'.
>> (push x place)
>>
>> Insert x at the head of the list stored in place.
>> Analogous to (setf place (cons x place)), though more careful about
>> evaluating each argument only once and in the right order.  place may
>> be a symbol, or any generalized variable allowed by `setf'.
>>
>> [back]
>>
>> M-x emacs-version RET
>> GNU Emacs 22.2.1 (x86_64-unknown-linux-gnu, X toolkit) of 2008-08-21 on simias
>
> Try emacs -Q.  Just because you choose to load some library overloading
> the default operators does not mean that other people should do the same
> when Emacs will provide those operators by default, with better
> performance.

Ah! :-)  

The cl package wouldn't be provided if the default had any performance at all...


(defvar *a* (cons nil nil))
(push 1 (car *a*))

Debugger entered--Lisp error: (wrong-type-argument symbolp (car *a*))
  (setq (car *a*) (cons 1 (car *a*)))
  (push 1 (car *a*))
  eval((push 1 (car *a*)))
  eval-last-sexp-1((4))
  eval-last-sexp((4))
  call-interactively(eval-last-sexp)


(require 'cl)
(push 1 (car *a*))
--> (1)
*a*
--> ((1))


-- 
__Pascal Bourguignon__

Re: Adding many elements to a list

[David Kastrup]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> David Kastrup <dak@gnu.org> writes:
>
>> pjb@anevia.com (Pascal J. Bourguignon) writes:
>>
>>> David Kastrup <dak@gnu.org> writes:
>>>
>>>> pjb@anevia.com (Pascal J. Bourguignon) writes:
>>>>
>>>>> David Kastrup <dak@gnu.org> writes:
>>>>>
>>>>>> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>>>>>>
>>>>>>> So better use (require 'cl) (push new-item list)
>>>>>>>    or (cons new-item list)
>>>>>>>    or (append (list new-items...) list)
>>>>>>
>>>>>> (require 'cl) is quite unnecessary for all of the mentioned
>>>>>> alternatives.
>>
>> Try emacs -Q.  Just because you choose to load some library
>> overloading the default operators does not mean that other people
>> should do the same when Emacs will provide those operators by
>> default, with better performance.
>
> Ah! :-)  
>
> The cl package wouldn't be provided if the default had any performance
> at all...
>
>
> (defvar *a* (cons nil nil))
> (push 1 (car *a*))

Well, consult its doc string for what it does and doesn't.  It's
basically the same issue as with setf/setq: the cl version of push does
a number of different things depending on a vague concept "location".
But you almost never need this sort of flexibility at runtime, and at
compile time, it obfuscates what actually happens, including the
possible performance impacts.

-- 
David Kastrup

Re: Adding many elements to a list

[Pascal J. Bourguignon]

David Kastrup <dak@gnu.org> writes:
> Well, consult its doc string for what it does and doesn't.  It's
> basically the same issue as with setf/setq: the cl version of push does
> a number of different things depending on a vague concept "location".
> But you almost never need this sort of flexibility at runtime, and at
> compile time, it obfuscates what actually happens, including the
> possible performance impacts.

You should write in assembler (what do I say, in binary!), because you
almost never need the flexibility that the bare push provide at
run-time, and at compilation time, it obfuscate what really happens,
including the possible performance impacts.

(disassemble (byte-compile (lambda (x) (push x *a*))))
-->
byte code:
  args: (x)
0       varref    x
1       varref    *a*
2       cons      
3       dup       
4       varset    *a*
5       return    

See?  There's a dup that's most often not used.  Performance IMPACT!

-- 
__Pascal Bourguignon__

Re: Adding many elements to a list

[David Kastrup]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> David Kastrup <dak@gnu.org> writes:
>> Well, consult its doc string for what it does and doesn't.  It's
>> basically the same issue as with setf/setq: the cl version of push
>> does a number of different things depending on a vague concept
>> "location".  But you almost never need this sort of flexibility at
>> runtime, and at compile time, it obfuscates what actually happens,
>> including the possible performance impacts.
>
> You should write in assembler (what do I say, in binary!), because you
> almost never need the flexibility that the bare push provide at
> run-time, and at compilation time, it obfuscate what really happens,
> including the possible performance impacts.

What use is winning when nobody wants to play with you anymore?

-- 
David Kastrup

Re: Adding many elements to a list

[Samuel Wales]

On Tue, Sep 22, 2009 at 05:16, David Kastrup <dak@gnu.org> wrote:
> But you almost never need this sort of flexibility at runtime, and at
> compile time, it obfuscates what actually happens, including the
> possible performance impacts.

Came in late to thread, but I tried disassembling setq and setf for
cases where place is not necessary, and got the same result.

(Please CC: me on any replies.)

Re: Adding many elements to a list

[Thierry Volpiatto]

David Kastrup <dak@gnu.org> writes:

> pjb@anevia.com (Pascal J. Bourguignon) writes:
>
>> David Kastrup <dak@gnu.org> writes:
>>
>>> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>>>
>>>> So better use (require 'cl) (push new-item list)
>>>>    or (cons new-item list)
>>>>    or (append (list new-items...) list)
>>>
>>> (require 'cl) is quite unnecessary for all of the mentioned
>>> alternatives.
>>
>> Not on emacs version < 23.
>
> Nonsense.  push&pop were officially announced in Emacs 21.1.  I may be
> mistaken, but I think they have been there even earlier.
>
> And the other options certainly were there from the earliest versions of
> GNU Emacs.

There is two implementation of push, one in cl that use setf and another
one in elisp (that doesn't need to require cl) that use cons.

-- 
A + Thierry Volpiatto
Location: Saint-Cyr-Sur-Mer - France

Re: Adding many elements to a list

[David Kastrup]

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)))

Where?  That's merely a side-effect.  As a stylistic rule of thumb, you
should not use nconc where concat would not also do the trick.  So in
this case, the proper usage would be

(setq l (nconc l '(c d)))

However, this particular use case is almost certainly _wrong_.  nconc is
a destructive operator, you should only use it on lists that were
constructed (consed) under _your_ control.  In this case, '(c d) has
been constructed under the control of the Lisp reader instead.  Using
nconc on it is certain to lead to trouble eventually.  To wit:

(setq l '(a b))
(dotimes (i 3) (nconc l '(c d)))

*Booooom*

Can you see what happens here?

If you don't have a clue about the ramifications of nconc, don't use it.

> I have noticed that this works in all cases except when l is nil.
> 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?

nil is not a cons cell.  So there is no car or cdr to set.

-- 
David Kastrup