From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Emanuel Berg Newsgroups: gmane.emacs.help Subject: Re: return first element in list with certain property Date: Tue, 21 Nov 2017 02:50:59 +0100 Message-ID: <86a7zgxuv0.fsf@zoho.com> References: <8660a60zjn.fsf@zoho.com> <87mv3gzndx.fsf@ericabrahamsen.net> <86ine4y7jy.fsf@zoho.com> <520f070f-331d-4cf9-ad17-0294f178171f@default> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1511229107 22852 195.159.176.226 (21 Nov 2017 01:51:47 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 21 Nov 2017 01:51:47 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4 (gnu/linux) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Tue Nov 21 02:51:43 2017 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eGxit-0005Z9-6V for geh-help-gnu-emacs@m.gmane.org; Tue, 21 Nov 2017 02:51:39 +0100 Original-Received: from localhost ([::1]:60520 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eGxj0-0002lL-N1 for geh-help-gnu-emacs@m.gmane.org; Mon, 20 Nov 2017 20:51:46 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:50797) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eGxiZ-0002l2-Og for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 20:51:20 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eGxiW-0008RL-Mb for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 20:51:19 -0500 Original-Received: from [195.159.176.226] (port=35702 helo=blaine.gmane.org) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1eGxiW-0008OF-FY for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 20:51:16 -0500 Original-Received: from list by blaine.gmane.org with local (Exim 4.84_2) (envelope-from ) id 1eGxiJ-0003hS-NN for help-gnu-emacs@gnu.org; Tue, 21 Nov 2017 02:51:03 +0100 X-Injected-Via-Gmane: http://gmane.org/ Mail-Followup-To: help-gnu-emacs@gnu.org Original-Lines: 59 Original-X-Complaints-To: usenet@blaine.gmane.org Mail-Copies-To: never Cancel-Lock: sha1:zfWspgJintmpHeXcJgF/bfx57mY= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 195.159.176.226 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.21 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.org@gnu.org Original-Sender: "help-gnu-emacs" Xref: news.gmane.org gmane.emacs.help:115020 Archived-At: Drew Adams wrote: > You see only one message for each element > tested because your predicate is called only > once per element. Yes, isn't that completely natural? > `cl-find-if' is implemented by first calling > `cl-position', which uses your predicate. > And then, once a satisfactory element is > found, it calls `elt' to traverse the list > again, to obtain that element. By "traverse" you mean go from the first element, to the second, and so on, until the element is found (or the list ends)? Or do you mean the entire thing is gone thru just like one would traverse a rock or... a traverse? But that doesn't make any sense WRT searching (as opposed to logistics)? If both `cl-position' and `elt' do this lineary, i.e. if this is the list (0 ... n) and the sought-after element has index e for (0 <= e <= n) then the worst-case for both are n, so combined 2n. However for this (cl-dolist (e test-list) (when (> e 1) (cl-return e) )) the worst-case is n! So both are linear, but, interestingly, the explicit iteration is twice as fast! I just wrote in another thread Using the primitive list-searching functions ‘memq’, ‘member’, ‘assq’, or ‘assoc’ is even faster than explicit iteration. It can be worth rearranging a data structure so that one of these primitive search functions can be used. [1] OK, so `cl-find-if' isn't mentioned or even a primitive, however it sure looks better than the `cl-dolist' above. But it isn't! So why does it use `etl'? [1] (info "(elisp) Compilation Tips") -- underground experts united http://user.it.uu.se/~embe8573