[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Appending to a list
From: |
Stefan Monnier |
Subject: |
Re: Appending to a list |
Date: |
Sun, 13 Dec 2020 17:43:46 -0500 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) |
>> `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.
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.
Stefan
- Appending to a list, steve-humphreys, 2020/12/13
- Re: Appending to a list, Joost Kremers, 2020/12/13
- Re: Appending to a list, Óscar Fuentes, 2020/12/13
- Re: Appending to a list, steve-humphreys, 2020/12/13
- Re: Appending to a list,
Stefan Monnier <=
- Re: Appending to a list, steve-humphreys, 2020/12/13
- Re: Appending to a list, Emanuel Berg, 2020/12/13
- Re: Appending to a list, steve-humphreys, 2020/12/13
- Re: Appending to a list, Emanuel Berg, 2020/12/13
- Re: Appending to a list, steve-humphreys, 2020/12/13
- Re: Appending to a list, Emanuel Berg, 2020/12/13
- Re: Appending to a list, steve-humphreys, 2020/12/13
- Re: Appending to a list, Michael Heerdegen, 2020/12/13
- Re: Appending to a list, Emanuel Berg, 2020/12/13
- Re: Appending to a list, steve-humphreys, 2020/12/13