Re: Appending to a list

[steve-humphreys]

> Sent: Sunday, December 13, 2020 at 11:43 PM
> From: "Stefan Monnier" <monnier@iro.umontreal.ca>
> To: help-gnu-emacs@gnu.org
> Subject: Re: Appending to a list
>
> >> `push` is what I would use:
> >>     (push "Swift" bird)
> >
> > This does not append.
> 
> Indeed, and it's a feature: append costs O(n), both in immediate CPU
> time and in memory allocations (which can increase memory use or at
> least increase the time spent in the GC) where `n` is the length of the
> list to which you append.  So if you do that O(n) times, you get an
> overall O(n²) complexity.

I don't care the way I insert.  If inserting in the beginning is more
efficient I would do that..  
 
> IOW, in most cases you're really better off with pushing to the
> beginning of the list, and if the order doesn't suit you, then use
> `reverse` afterwards, which will still be O(n) overall rather than
> O(n²).
> 
> >> No need to use `setq` here.
> >>
> >> `push` won't check if the element is already in the list, though. You can 
> >> use
> >> `cl-pushnew` in that case, but be sure to load the library it's in:
> >>
> >>     (require 'cl-lib)
> >>     (cl-pushnew "Swift" bird)
> > Isn't that the same as
> > (add-to-list bird "Swift" t)
> 
> Not quite:
> 
> - your `t` at the end makes `add-to-list` add to the rear of the
>   list whereas `cl-pushnew` adds it to the front.
> - `add-to-list` would require you to quote the variable symbol, as in:
> 
>       (add-to-list 'bird "Swift" t)
> 
> - `add-to-list` cannot operate on a lexically scoped `bird` variable.
> 
> - `add-to-list` cannot operate on generalized variables, whereas
>   `cl-pushnew` (just like `push`) will be happy with things like
> 
>       (cl-pushnew "Swift" (gethash "birds" table))
> 
> - `cl-pushnew` by default compares with `eql` whereas here you'd likely
>   want to compare with `equal`, like `add-to-list` does, so you'd need:
> 
>       (cl-pushnew "Swift" bird :test #'equal)
> 
> BTW `push` is significantly faster than either of `add-to-list` or
> `cl-pushnew` since it doesn't need to check in O(n) time if the
> element is already on the list.
 

I am thinking using push if there are only few caveats when using it,
compared to the other ones.
 
>         Stefan
> 
> 
>