unofficial mirror of help-gnu-emacs@gnu.org
 help / color / mirror / Atom feed
From: Stefan Monnier <monnier@iro.umontreal.ca>
To: help-gnu-emacs@gnu.org
Subject: Re: Appending to a list
Date: Sun, 13 Dec 2020 17:43:46 -0500	[thread overview]
Message-ID: <jwvpn3djq5n.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: 87sg89v1f7.fsf@telefonica.net

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




  parent reply	other threads:[~2020-12-13 22:43 UTC|newest]

Thread overview: 32+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-12-13 20:46 Appending to a list steve-humphreys
2020-12-13 21:03 ` Joost Kremers
2020-12-13 21:30   ` Óscar Fuentes
2020-12-13 21:46     ` steve-humphreys
2020-12-13 22:37     ` Joost Kremers
2020-12-13 23:08       ` Joost Kremers
2020-12-13 22:43     ` Stefan Monnier [this message]
2020-12-13 23:25       ` steve-humphreys
2020-12-13 23:33         ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14  0:19           ` steve-humphreys
2020-12-14  0:37             ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14  2:54               ` steve-humphreys
2020-12-14  2:58                 ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14  3:23                   ` steve-humphreys
2020-12-14  4:07                 ` Michael Heerdegen
2020-12-14  4:16                   ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14  4:23                   ` steve-humphreys
2020-12-14  4:50                     ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14  5:13                       ` steve-humphreys
2020-12-14  6:20                         ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14  6:25                           ` steve-humphreys
2020-12-14  5:28                       ` steve-humphreys
2020-12-14  6:26                         ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14 10:25                           ` steve-humphreys
2020-12-14  5:55                       ` steve-humphreys
2020-12-14  6:36                         ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-14 17:22                     ` Michael Heerdegen
2020-12-14 18:25                       ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-15  0:17                         ` steve-humphreys
2020-12-15  1:38                           ` Emanuel Berg via Users list for the GNU Emacs text editor
2020-12-13 21:41   ` steve-humphreys
2020-12-13 23:31     ` Emanuel Berg via Users list for the GNU Emacs text editor

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/emacs/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=jwvpn3djq5n.fsf-monnier+emacs@gnu.org \
    --to=monnier@iro.umontreal.ca \
    --cc=help-gnu-emacs@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).