help-gnu-emacs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: return first element in list with certain property


From: Eric Abrahamsen
Subject: Re: return first element in list with certain property
Date: Mon, 20 Nov 2017 12:49:30 -0800
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux)

Drew Adams <drew.adams@oracle.com> 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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]