From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Emanuel Berg Newsgroups: gmane.emacs.help Subject: Re: [External] : Use of an associated list with completing-read Date: Sat, 20 Apr 2024 03:59:20 +0200 Message-ID: <87r0f0ssjr.fsf@dataswamp.org> References: <1ZznhcKDmGMQcjaA3pyQaBOnYG81YwX4pE1YSoGxi_Vj_UFqz_DzTcdhZ50XnL3lEDivoq5THtGr-ShAq1PMbkmNHxajYrXWeRmti6_BSD4=@protonmail.com> <6IDPPDE6NaK72davfT7rnK8S553m9H8sBdCDy8UqV81_uCoMjrGuIjErQYACxxx5LZjd2Np0R9S2RPCqIFanRLNpVZhEGvXNYfqBrYI0ahw=@protonmail.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="478"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) To: help-gnu-emacs@gnu.org Cancel-Lock: sha1:a0RfK8ExiixhcHiH7wd7bTEXNgw= Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Sat Apr 20 10:28:19 2024 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 1ry655-000AVW-8l for geh-help-gnu-emacs@m.gmane-mx.org; Sat, 20 Apr 2024 10:28:19 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ry64R-00040e-7a; Sat, 20 Apr 2024 04:27:39 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ry00u-0004Mw-4p for help-gnu-emacs@gnu.org; Fri, 19 Apr 2024 21:59:37 -0400 Original-Received: from ciao.gmane.io ([116.202.254.214]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ry00n-00041y-RA for help-gnu-emacs@gnu.org; Fri, 19 Apr 2024 21:59:34 -0400 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1ry00l-000Adr-M1 for help-gnu-emacs@gnu.org; Sat, 20 Apr 2024 03:59:27 +0200 X-Injected-Via-Gmane: http://gmane.org/ Mail-Followup-To: help-gnu-emacs@gnu.org Mail-Copies-To: never 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.248, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Sat, 20 Apr 2024 04:27:38 -0400 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.29 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-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.help:146398 Archived-At: Stefan Monnier via Users list for the GNU Emacs text editor wrote: >> An even more common cliche for doing the same thing is to >> do #1, then (2) cons instead of append, and (3) when >> finished adding list elements, do an `nreverse' of the list >> you created. That too is a destructive operation. > > That's the usual solution, with the desired linear (i.e. > optimal) complexity, indeed. AKA O(N) which is linear, or proportional to the problem size N. Even better is constant complexity, O(1), where it does not matter how big the problem is, since that, N, isn't even in the equation, as we saw. Probably not possible in a lot of cases, including this one. -- underground experts united https://dataswamp.org/~incal