From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Eric Abrahamsen Newsgroups: gmane.emacs.help Subject: Re: return first element in list with certain property Date: Mon, 20 Nov 2017 12:49:30 -0800 Message-ID: <87mv3gzndx.fsf@ericabrahamsen.net> References: <8660a60zjn.fsf@zoho.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1511211014 17712 195.159.176.226 (20 Nov 2017 20:50:14 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 20 Nov 2017 20:50:14 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Mon Nov 20 21:50:10 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 1eGt16-0004Bi-1n for geh-help-gnu-emacs@m.gmane.org; Mon, 20 Nov 2017 21:50:08 +0100 Original-Received: from localhost ([::1]:59673 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eGt1D-0000x1-5W for geh-help-gnu-emacs@m.gmane.org; Mon, 20 Nov 2017 15:50:15 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:48015) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eGt0l-0000wt-Ct for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 15:49:51 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eGt0g-0003g9-TN for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 15:49:47 -0500 Original-Received: from [195.159.176.226] (port=49044 helo=blaine.gmane.org) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1eGt0g-0003ZL-MF for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 15:49:42 -0500 Original-Received: from list by blaine.gmane.org with local (Exim 4.84_2) (envelope-from ) id 1eGt0U-00020n-FO for help-gnu-emacs@gnu.org; Mon, 20 Nov 2017 21:49:30 +0100 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 50 Original-X-Complaints-To: usenet@blaine.gmane.org Cancel-Lock: sha1:GTrjusQ40nnpBnw5FMaep8F29mM= 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:115010 Archived-At: Drew Adams writes: >>> cl-find-if >> >> That's it 100% > > BTW, I haven't run any tests, but the `cl-find' code, which > is used also by functions such as `cl-find-if', apparently > traverses the list twice: Once when it calls `cl-position' > and a second time when it calls `elt'. > > (defun cl-find (cl-item cl-seq &rest cl-keys) > (let ((cl-pos (apply 'cl-position cl-item cl-seq cl-keys))) > (and cl-pos (elt cl-seq cl-pos)))) > > `cl-position' does this for a list - it cdrs down list CL-P: > > (let ((cl-p (nthcdr cl-start cl-seq))) > (or cl-end (setq cl-end 8000000)) > (let ((cl-res nil)) > (while (and cl-p (< cl-start cl-end) > (or (not cl-res) cl-from-end)) > (if (cl--check-test cl-item (car cl-p)) > (setq cl-res cl-start)) > (setq cl-p (cdr cl-p) cl-start (1+ cl-start))) > cl-res)) > > Checking the C source for `elt' called on a list (admittedly, > somewhat old C source code, which is all I have at hand), it > does, in effect, (car (nthcdr n list)). It cdrs down LIST. > > Someone might want to profile the difference, for a long list > whose first occurrence for the sought item is near the end of > the list. Maybe compare, for example, the use of `cl-find-if' > with something simple that traverses the list only once: > > (catch '>1 > (dolist (x xs nil) (when (> x 1) (throw '>1 x)))) FWIW, this is essentially how seq-find works, and I generally use this. I once tried making a binary-search for very long lists that are sorted, but I suppose that could be much worse, since you're potentially traversing (a part of) the list four or five as you zero in on the element. `delete-dups' is also instructional: it uses a different strategy, with a hash table, for lists longer than 100 elements. Eric