[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
- Re: return first element in list with certain property, (continued)
- Re: return first element in list with certain property, Eric Abrahamsen, 2017/11/19
- Re: return first element in list with certain property, Philipp Stephani, 2017/11/19
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/19
- Re: return first element in list with certain property, John Mastro, 2017/11/20
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/20
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/20
- Re: return first element in list with certain property, John Mastro, 2017/11/20
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/20
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/20
RE: return first element in list with certain property, Drew Adams, 2017/11/20
- Re: return first element in list with certain property,
Eric Abrahamsen <=
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/20
- Re: return first element in list with certain property, Eric Abrahamsen, 2017/11/20
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/20
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/20
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/21
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/21
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/21
- Re: return first element in list with certain property, Nicolas Petton, 2017/11/22
Re: return first element in list with certain property, Nicolas Petton, 2017/11/22
Re: return first element in list with certain property, Philipp Stephani, 2017/11/21