[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: return first element in list with certain property
From: |
Emanuel Berg |
Subject: |
Re: return first element in list with certain property |
Date: |
Tue, 21 Nov 2017 02:50:59 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.4 (gnu/linux) |
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
- Re: return first element in list with certain property, (continued)
- Re: return first element in list with certain property, Eli Zaretskii, 2017/11/25
- Re: return first element in list with certain property, tomas, 2017/11/25
- Re: return first element in list with certain property, John Mastro, 2017/11/25
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/25
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/26
- RE: return first element in list with certain property, Drew Adams, 2017/11/20
- Re: return first element in list with certain property,
Emanuel Berg <=
Re: return first element in list with certain property, Marco Wahl, 2017/11/19
Re: return first element in list with certain property, Marco Wahl, 2017/11/19