From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.help Subject: Re: Appending to a list Date: Sun, 13 Dec 2020 17:43:46 -0500 Message-ID: References: <877dpljtwg.fsf@fastmail.fm> <87sg89v1f7.fsf@telefonica.net> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="33558"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) To: help-gnu-emacs@gnu.org Cancel-Lock: sha1:IgMpYGmDATnKOOe+7Hw2H0vpAp0= Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Sun Dec 13 23:44:31 2020 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1koa6R-0008eV-3h for geh-help-gnu-emacs@m.gmane-mx.org; Sun, 13 Dec 2020 23:44:31 +0100 Original-Received: from localhost ([::1]:41464 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1koa6Q-0004GN-4k for geh-help-gnu-emacs@m.gmane-mx.org; Sun, 13 Dec 2020 17:44:30 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:42106) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1koa5t-0004G1-Jq for help-gnu-emacs@gnu.org; Sun, 13 Dec 2020 17:43:57 -0500 Original-Received: from static.214.254.202.116.clients.your-server.de ([116.202.254.214]:55864 helo=ciao.gmane.io) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1koa5s-0007rN-6v for help-gnu-emacs@gnu.org; Sun, 13 Dec 2020 17:43:57 -0500 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1koa5o-00080b-DC for help-gnu-emacs@gnu.org; Sun, 13 Dec 2020 23:43:52 +0100 X-Injected-Via-Gmane: http://gmane.org/ Received-SPF: pass client-ip=116.202.254.214; envelope-from=geh-help-gnu-emacs@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: -16 X-Spam_score: -1.7 X-Spam_bar: - X-Spam_report: (-1.7 / 5.0 requ) BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.249, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "help-gnu-emacs" Xref: news.gmane.io gmane.emacs.help:126329 Archived-At: >> `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