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] : Re: Testing whether a list contains at least one non-nil element Date: Thu, 27 Oct 2022 07:30:21 +0200 Message-ID: <87tu3prfyq.fsf@dataswamp.org> References: <87r0yw85la.fsf@dataswamp.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="34641"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) To: help-gnu-emacs@gnu.org Cancel-Lock: sha1:A6gDScOIZVJcOtCJ27AaO1BZsk0= Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Thu Oct 27 13:13:34 2022 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 1oo0pK-0008oH-IV for geh-help-gnu-emacs@m.gmane-mx.org; Thu, 27 Oct 2022 13:13:34 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oo0ou-0003XI-Tj; Thu, 27 Oct 2022 07:13:09 -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 1onvTO-0005pI-Nf for help-gnu-emacs@gnu.org; Thu, 27 Oct 2022 01:30:38 -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 1onvTM-0000hg-Kb for help-gnu-emacs@gnu.org; Thu, 27 Oct 2022 01:30:34 -0400 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1onvTJ-0008wD-VG for help-gnu-emacs@gnu.org; Thu, 27 Oct 2022 07:30:29 +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.249, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Thu, 27 Oct 2022 07:13:07 -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: , Original-Sender: "help-gnu-emacs" Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.help:140427 Archived-At: Jean Louis wrote: >> You certainly don't need to remove all nils from the list. >> If your list is 100,000,000 elements long and the first >> element is t, why would you want to copy the entire list >> and then remove all the nils from it? Testing the first >> element tells you the answer. > > [...] What I know is that by testing the first element does > not tell the answer if list has any non nil element: > > (let ((my-list '(nil nil nil nil))) > (car my-list)) ⇒ nil > > (let ((my-list '(nil nil nil nil 1))) > (car my-list)) ⇒ nil > > So testing the first element did not give me the answer that > my-list has one non-nil element. He means that case shows how poor that solution would be, which means it's just not a good solution. There are several ways to search a list for a specific element but they rely on sorting the list first and if that isn't desired is there really any other way than to examine the items one by one? In that case it's the Linear Search algorithm which is at worst O(n), i.e. the whole list has to be searched until the element is found at the last element or not found at all. OTOH if sorting is done then one does Quick Sort first, which is at worst O(n^2), then Binary Search on the result which is at worst O(log n), so combined they are, at worst, worse than O(n^2) or in other words, much worse than Linear Search at O(n). However if the data is *kept* sorted after the sorting and insertions are made in a way that will uphold the order, that means Binary Search can be used directly, that means we are at a much better O(log n) again compared to Linear Search at O(n) ... -- underground experts united https://dataswamp.org/~incal