return first element in list with certain property

return first element in list with certain property

[Emanuel Berg]

What is considered the right way to return the
first element in list that has
a certain property?

The best way I've found so far is `cl-some' and
then `and'. While I don't consider the
"`and' hack" to be detrimental in any way I was
curious if there was a complete
"hack free" way...

Example: get the first element that is bigger
than 1:

    (cl-some (lambda (e) (and (> e 1) e)) '(1 1 3 1 4 2)) ; 3

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Eric Abrahamsen]

Emanuel Berg <moasen@zoho.com> writes:

> What is considered the right way to return the
> first element in list that has
> a certain property?
>
> The best way I've found so far is `cl-some' and
> then `and'. While I don't consider the
> "`and' hack" to be detrimental in any way I was
> curious if there was a complete
> "hack free" way...
>
> Example: get the first element that is bigger
> than 1:
>
>     (cl-some (lambda (e) (and (> e 1) e)) '(1 1 3 1 4 2)) ; 3

I think `cl-find' is what I use for this, with the :test keyword. Or
`seq-find' seems to do the same thing.

Re: return first element in list with certain property

[Marco Wahl]

Emanuel Berg <moasen@zoho.com> writes:

> What is considered the right way to return the
> first element in list that has
> a certain property?
>
> The best way I've found so far is `cl-some' and
> then `and'. While I don't consider the
> "`and' hack" to be detrimental in any way I was
> curious if there was a complete
> "hack free" way...
>
> Example: get the first element that is bigger
> than 1:
>
>     (cl-some (lambda (e) (and (> e 1) e)) '(1 1 3 1 4 2)) ; 3

(cl-loop for e in '(1 1 3 1 4 2)
         when (> e 1)
         return e)

lgtm

Re: return first element in list with certain property

[Marco Wahl]

Emanuel Berg <moasen@zoho.com> writes:

> What is considered the right way to return the
> first element in list that has
> a certain property?
>
> The best way I've found so far is `cl-some' and
> then `and'. While I don't consider the
> "`and' hack" to be detrimental in any way I was
> curious if there was a complete
> "hack free" way...
>
> Example: get the first element that is bigger
> than 1:
>
>     (cl-some (lambda (e) (and (> e 1) e)) '(1 1 3 1 4 2)) ; 3

(cl-loop for e in '(1 1 3 1 4 2)
         when (> e 1)
         return e)

lgtm

Re: return first element in list with certain property

[Philipp Stephani]

Emanuel Berg <moasen@zoho.com> schrieb am So., 19. Nov. 2017 um 21:44 Uhr:

> What is considered the right way to return the
> first element in list that has
> a certain property?
>
> The best way I've found so far is `cl-some' and
> then `and'. While I don't consider the
> "`and' hack" to be detrimental in any way I was
> curious if there was a complete
> "hack free" way...
>

cl-find-if

Re: return first element in list with certain property

[Emanuel Berg]

Marco Wahl wrote:

>> What is considered the right way to return
>> the first element in list that has a certain
>> property? The best way I've found so far is
>> `cl-some' and then `and'. While I don't
>> consider the "`and' hack" to be detrimental
>> in any way I was curious if there was
>> a complete "hack free" way... Example: get
>> the first element that is bigger than 1:
>> (cl-some (lambda (e) (and (> e 1) e)) '(1 1
>> 3 1 4 2)) ; 3
>
> (cl-loop for e in '(1 1 3 1 4 2) when (> e 1)
> return e)

Much worse than mine :)

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

Philipp Stephani wrote:

>> What is considered the right way to return
>> the first element in list that has a certain
>> property? The best way I've found so far is
>> `cl-some' and then `and'. While I don't
>> consider the "`and' hack" to be detrimental
>> in any way I was curious if there was
>> a complete "hack free" way...
>>
>
> cl-find-if

That's it 100%

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[John Mastro]

Emanuel Berg <moasen@zoho.com> wrote:
> Philipp Stephani wrote:
>> cl-find-if
>
> That's it 100%

Or, if seq.el is more your style:

(seq-find (lambda (e) (> e 1)) '(1 1 3 1 4 2))
;=> 3

        John

Re: return first element in list with certain property

[Michael Heerdegen]

John Mastro <john.b.mastro@gmail.com> writes:

> >> cl-find-if
> >
> > That's it 100%
>
> Or, if seq.el is more your style:
>
> (seq-find (lambda (e) (> e 1)) '(1 1 3 1 4 2))
> ;=> 3

And if you want to be cool:

(seq-find (apply-partially #'< 1) '(1 1 3 1 4 2))
==> 3


Michael.

RE: return first element in list with certain property

[Drew Adams]

>> 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))))

The idiom of traversing a list only once, throwing to a
`catch', is a pretty good one to learn, I think.  It's
straightforward and transparent, doing just what it says.

Granted, it doesn't shout "Return the first element > 1."

And it's a little more verbose than using a higher
abstraction such as `cl-find-if'.  Anyway, compare the
length of the code above with these - a difference, but
not huge:

(seq-find (apply-partially #'< 1) xs)
(seq-find (lambda (x) (> x 1)) xs)
(cl-find-if (lambda (x) (> x 1)) xs)
(cl-loop for x in xs when (> x 1) return x)
(cl-some (lambda (x) (and (> x 1) x)) xs)

Dunno whether the other functions, besides `cl-find-if',
traverse the list more than once.

Maybe the code defining `cl-find' should be tweaked to
avoid two traversals?  `cl-position' traverses only once,
and so does `elt'.  Maybe getting the position in the list
and then cdring down the list again to that position is
not the smartest way to do `cl-find-if' on a list.

Re: return first element in list with certain property

[Eric Abrahamsen]

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

[Emanuel Berg]

John Mastro wrote:

> Or, if seq.el is more your style:
>
> (seq-find (lambda (e) (> e 1)) '(1 1 3 1 4 2)) ;=> 3

(require 'seq)
(seq-find   (lambda (e) (> e 1)) '(1 1 3 1 4 2)) ; 3

(require 'cl-lib)
(cl-find-if (lambda (e) (> e 1)) '(1 1 3 1 4 2)) ; 3

The syntax seems pretty identical to me so
perhaps you can tell me more about the
seq package?

I have never required `seq' before, CL tho 21
times. So I'll stick to even more CL unless you
can show the court some chocking new
evidence...

--
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

Eric Abrahamsen wrote:

> FWIW, this is essentially how seq-find works,
> and I generally use this.

Here (my use case) it is important that the
search is linear along the list from the
beginning as the hit is almost always in the
very early section of the list.

However the below tests seem to indicate no
problems for any of the solutions suggested
so far?

(let ((test-list '(0 1 2 3 4 5)))

  (cl-dolist (e test-list)
    (message "cl-dolist processing: %s" e)
    (when (> e 1) (cl-return e) ))

  (cl-find-if (lambda (e) (and (message "cl-find-if processing: %s" e)
                               (> e 1) ))
              test-list)

  (seq-find   (lambda (e) (and (message "find-seq processing: %s" e)
                               (> e 1) ))
              test-list)
  )
;; cl-dolist processing: 0
;; cl-dolist processing: 1
;; cl-dolist processing: 2
;; cl-find-if processing: 0
;; cl-find-if processing: 1
;; cl-find-if processing: 2
;; find-seq processing: 0
;; find-seq processing: 1
;; find-seq processing: 2

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

Michael Heerdegen wrote:

> And if you want to be cool:
>
> (seq-find (apply-partially #'< 1) '(1 1 3 1 4
> 2)) ==> 3

"And" if you want to be cool? I agree
`apply-partially' is cooler but why is
`seq-find' better than `cl-find-if'?

Actually no one said it was better. The only
thing said was that it was my style. Eheh.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[John Mastro]

Emanuel Berg <moasen@zoho.com> wrote:
> Michael Heerdegen wrote:
>
>> And if you want to be cool:
>>
>> (seq-find (apply-partially #'< 1) '(1 1 3 1 4
>> 2)) ==> 3
>
> "And" if you want to be cool? I agree
> `apply-partially' is cooler but why is
> `seq-find' better than `cl-find-if'?
>
> Actually no one said it was better. The only
> thing said was that it was my style. Eheh.

I didn't say anything about your style. I pointed out that "if seq.el is
more your style" (in other words, "if you prefer seq.el"), seq-find also
works for this.

        John

Re: return first element in list with certain property

[Eric Abrahamsen]

Emanuel Berg <moasen@zoho.com> writes:

> Eric Abrahamsen wrote:
>
>> FWIW, this is essentially how seq-find works,
>> and I generally use this.
>
> Here (my use case) it is important that the
> search is linear along the list from the
> beginning as the hit is almost always in the
> very early section of the list.

In that case there will be less difference between the two: as Drew
noted, `cl-find-if' will traverse the list twice, which only becomes a
big problem if the desired element is at the end of the list.

But enough speculation!

(setq test-front (append '(1 1 3) (make-list 1000 1)))

(setq test-back (append (make-list 1000 1) '(3 1 1)))

(benchmark 1000 '(seq-find (lambda (elt) (= 3 elt)) test-front))
"Elapsed time: 0.008247s"

(benchmark 1000 '(cl-find-if (lambda (elt) (= 3 elt)) test-front))
"Elapsed time: 0.006165s"

(benchmark 1000 '(seq-find (lambda (elt) (= 3 elt)) test-back))
"Elapsed time: 0.134623s"

(benchmark 1000 '(cl-find-if (lambda (elt) (= 3 elt)) test-back))
"Elapsed time: 0.167007s"

Yup, in your case it doesn't matter too much.

Eric

Re: return first element in list with certain property

[Michael Heerdegen]

Emanuel Berg <moasen@zoho.com> writes:

> > And if you want to be cool:
> >
> > (seq-find (apply-partially #'< 1) '(1 1 3 1 4
> > 2)) ==> 3
>
> "And" if you want to be cool? I agree `apply-partially' is cooler but
>  why is `seq-find' better than `cl-find-if'?

I (too) didn't want to imply that.  Both functions are defined, so both
are there to be used.


Michael.

RE: return first element in list with certain property

[Drew Adams]

> However the below tests seem to indicate no
> problems for any of the solutions suggested
> so far?

Certainly there will be no problem with any of them
when the list is small.

> (let ((test-list '(0 1 2 3 4 5)))
> 
>   (cl-dolist (e test-list)
>     (message "cl-dolist processing: %s" e)
>     (when (> e 1) (cl-return e) ))
> 
>   (cl-find-if (lambda (e) (and (message "cl-find-if processing: %s" e)
>                                (> e 1) ))
>               test-list)
> 
>   (seq-find   (lambda (e) (and (message "find-seq processing: %s" e)
>                                (> e 1) ))
>               test-list)
>   )
> ;; cl-dolist processing: 0
> ;; cl-dolist processing: 1
> ;; cl-dolist processing: 2
> ;; cl-find-if processing: 0
> ;; cl-find-if processing: 1
> ;; cl-find-if processing: 2
> ;; find-seq processing: 0
> ;; find-seq processing: 1
> ;; find-seq processing: 2

As I said, `cl-find-if' apparently traverses the list twice.

You see only one message for each element tested because your
predicate is called only once per element.  `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.  The call to `elt' does not use your predicate, so
you see no messages for it.

As I said, I have not bothered to profile the different
suggestions, but a guess is that with a very large list
`cl-find-if' will be slower.

Re: return first element in list with certain property

[Emanuel Berg]

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

[Emanuel Berg]

Eric Abrahamsen wrote:

> In that case there will be less difference
> between the two: as Drew noted, `cl-find-if'
> will traverse the list twice, which only
> becomes a big problem if the desired element
> is at the end of the list.

It doesn't have to be a problem, it is bizarre
as it is. Thanks for mentioning it, I'll change
to `seq-find'.

See, my intuition was right, seq-find *is*
better even tho you guys are in denial about
it :)

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

YT wrote:

> It doesn't have to be a problem, it is
> bizarre as it is. Thanks for mentioning it,
> I'll change to `seq-find'.

Not so fast.
O K A Y ...
I t  s e e m s  `seq-find' i s  n o t  i n
E m a c s  b u t  i n  seq-24.el .

However CL is, so shockingly, this is the best
by far - worst-case n, and with all the fixings
available from the get-go!

    (cl-dolist (e test-list)
      (when (> e 1) (cl-return e) ))

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

Marco Wahl wrote:

> (cl-loop for e in '(1 1 3 1 4 2) when (> e 1)
> return e)
>
> lgtm

+1 only I prefer the dolist syntax.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Michael Heerdegen]

Emanuel Berg <moasen@zoho.com> writes:

> I t  s e e m s  `seq-find' i s  n o t  i n
> E m a c s  b u t  i n  seq-24.el .

It is in Emacs.  seq-24.el was a special version of seq.el adapted
(backported) to Emacs 24, since some things had to be done differently
in this Emacs version.


Michael.

Re: return first element in list with certain property

[Philipp Stephani]

Emanuel Berg <moasen@zoho.com> schrieb am Di., 21. Nov. 2017 um 02:55 Uhr:

> Eric Abrahamsen wrote:
>
> > In that case there will be less difference
> > between the two: as Drew noted, `cl-find-if'
> > will traverse the list twice, which only
> > becomes a big problem if the desired element
> > is at the end of the list.
>
> It doesn't have to be a problem, it is bizarre
> as it is. Thanks for mentioning it, I'll change
> to `seq-find'.
>
> See, my intuition was right, seq-find *is*
> better even tho you guys are in denial about
> it :)
>

Please consider Knuth's statement about premature optimization. Until your
users have actually complained about the speed of your product and you have
benchmarked it and isolated cl-find-if as the culprit, there's no need to
micro-optimize. Presumably cl-find-if has performed two iterations for
years or decades without anybody being bothered enough to improve it.

Re: return first element in list with certain property

[Michael Heerdegen]

Philipp Stephani <p.stephani2@gmail.com> writes:

> Please consider Knuth's statement about premature optimization. Until
> your users have actually complained about the speed of your product
> and you have benchmarked it and isolated cl-find-if as the culprit,
> there's no need to micro-optimize. Presumably cl-find-if has performed
> two iterations for years or decades without anybody being bothered
> enough to improve it.

Not only that.  Seems the second iteration is at least ~50 times faster
than the first one (using `elt' that is much faster than a loop), so it
doesn't matter anyway.  If your program is slow, the second iteration
will never be the culprit.


Michael.

RE: return first element in list with certain property

[Drew Adams]

> Please consider Knuth's statement about premature optimization. Until
> your users have actually complained about the speed of your product and you
> have benchmarked it and isolated cl-find-if as the culprit, there's no need to
> micro-optimize.

100% agreement.

> Presumably cl-find-if has performed two iterations for years
> or decades without anybody being bothered enough to improve it.

"Presumably ..."  No.

Yes, cl.el has been here for a long time.  But that doesn't
mean that everything in it is implemented as well as it
could be.

It was put together in a fairly short time, and it has _not_
had super heavy use over the years (that's my guess).

And yes, Emacs lisp use (including of CL emulation) is mostly
for Emacs, and most use cases do not involve things that need
high performance.  The number of cases where `cl-find' has
actually been used on very large lists is likely not so high.

Looking at the code, it seems that it would not be difficult
to improve this aspect, providing just a single traversal.
For the list case it could just use the catch-throw idiom,
for example.

So yes, not choosing to use `cl-find' in your Emacs-Lisp
code just because it traverses the list twice is silly and
is most likely premature optimization.

But fixing the `cl-find' implementation so that it does not
gratuitously traverse the list twice might not be silly.

As those tests communicated here so far have shown, `cl-find'
is anyway performant - no doubt partly because `elt' has a
C implementation.  Still, the double traversal is gratuitous,
and `cl-find' would be faster without it.

(Do I personally care about how fast it is?  Not really.)

Re: return first element in list with certain property

[Emanuel Berg]

Michael Heerdegen wrote:

> It is in Emacs. seq-24.el was a special
> version of seq.el adapted (backported) to
> Emacs 24, since some things had to be done
> differently in this Emacs version.

OK, so is it different in Emacs 25? Or is one
still supposed to get seq.el from ELPA, only
with no backport hassle?

There is where I got the whole thing (I guess,
tho I don't remember the occasion) and the
source is located in the .emacs.d dir in my
home dir.

When I can do the virtually the same with CL
which is readily available it doesn't feel
motivated to put this on presumable users to go
fetch seq just for this.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

Philipp Stephani wrote:

> Please consider Knuth's statement about
> premature optimization. Until your users have
> actually complained about the speed of your
> product and you have benchmarked it and
> isolated cl-find-if as the culprit, there's
> no need to micro-optimize.
> Presumably cl-find-if has performed two
> iterations for years or decades without
> anybody being bothered enough to improve it.

This is not an optimization issue in my eyes.
It is just bizarre to have low-level operators
on low-level data structures operate like this
when there is no reason to, as the `cl-loop',
`cl-dolist' and `seq-find' examples all show.
It is like the basic building blocks of the
universe. Better get them right.
I'm a bottom-up guy.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

Drew Adams wrote:

> So yes, not choosing to use `cl-find' in your
> Emacs-Lisp code just because it traverses the
> list twice is silly and is most likely
> premature optimization.

So yes, you are silly.

> (Do I personally care about how fast it is?
> Not really.)

I don't care twice as much.

-- 
underground experts united
http://user.it.uu.se/~embe8573

RE: return first element in list with certain property

[Drew Adams]

> > So yes, not choosing to use `cl-find' in your
> > Emacs-Lisp code just because it traverses the
> > list twice is silly and is most likely
> > premature optimization.
> 
> So yes, you are silly.

I didn't choose not to use `cl-find'.  Did you?
For that reason alone ("just because")?

FWIW, I tend to use just the catch-throw idiom,
partly because some of my code supports also
Emacs versions that predate `cl-lib.el'.

But I don't think I have any code that searches
long enough lists that such performance
considerations would be worthwhile.

Re: return first element in list with certain property

[Michael Heerdegen]

Emanuel Berg <moasen@zoho.com> writes:

> When I can do the virtually the same with CL which is readily
> available it doesn't feel motivated to put this on presumable users to
> go fetch seq just for this.

If your package package-requires "seq", the package manager should
install the thing automatically when appropriate.  I'm not sure about
Emacsen with major version < 24, though.

Of course you can also just use the cl thing.


Michael.

Re: return first element in list with certain property

[James K. Lowden]

On Tue, 21 Nov 2017 19:37:01 +0100
Michael Heerdegen <michael_heerdegen@web.de> wrote:

> Philipp Stephani <p.stephani2@gmail.com> writes:
> 
> > Please consider Knuth's statement about premature optimization.
> > Until your users have actually complained about the speed of your
> > product and you have benchmarked it and isolated cl-find-if as the
> > culprit, there's no need to micro-optimize. Presumably cl-find-if
> > has performed two iterations for years or decades without anybody
> > being bothered enough to improve it.
> 
> Not only that.  Seems the second iteration is at least ~50 times
> faster than the first one (using `elt' that is much faster than a
> loop), so it doesn't matter anyway.  If your program is slow, the
> second iteration will never be the culprit.

Not only that.  ;-)   Traversing the list twice is still O(n).  

I would guess in elisp the typical list is on the order of a dozen
elements.  As Rob Pike says,"Fancy algorithms are slow for small N, and
N is almost always small."  

 No matter how long the list is, it traversing it twice will only take
at most twice as long.  If your design fails when your data size
doubles, you have problems emacs won't solve.  

--jkl

Re: return first element in list with certain property

[Michael Heerdegen]

"James K. Lowden" <jklowden@speakeasy.net> writes:

> No matter how long the list is, it traversing it twice will only take
> at most twice as long.

Hey, you would not say that if you had to traverse the list yourself ;-)

When I optimize my own code, I always imagine I would have to perform
the algorithm myself.  Then you get a good feeling where it's worth to
optimize and where not.


Michael.

Re: return first element in list with certain property

[Emanuel Berg]

James K. Lowden wrote:

> I would guess in elisp the typical list is on
> the order of a dozen elements. As Rob Pike
> says,"Fancy algorithms are slow for small N,
> and N is almost always small."

But here it is not a matter of fancy algorithms
to do it in N. Actually the one implemented to
do it in 2N seems "fancier" to me, if that is
the word.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Rusi]

On Wednesday, November 22, 2017 at 9:22:18 AM UTC+5:30, James K. Lowden wrote:
> On Tue, 21 Nov 2017 19:37:01 +0100
> Michael Heerdegen wrote:
> 
> > Philipp Stephani  writes:
> > 
> > > Please consider Knuth's statement about premature optimization.
> > > Until your users have actually complained about the speed of your
> > > product and you have benchmarked it and isolated cl-find-if as the
> > > culprit, there's no need to micro-optimize. Presumably cl-find-if
> > > has performed two iterations for years or decades without anybody
> > > being bothered enough to improve it.
> > 
> > Not only that.  Seems the second iteration is at least ~50 times
> > faster than the first one (using `elt' that is much faster than a
> > loop), so it doesn't matter anyway.  If your program is slow, the
> > second iteration will never be the culprit.
> 
> Not only that.  ;-)   Traversing the list twice is still O(n).  
> 
> I would guess in elisp the typical list is on the order of a dozen
> elements.  As Rob Pike says,"Fancy algorithms are slow for small N, and
> N is almost always small."  
> 
>  No matter how long the list is, it traversing it twice will only take
> at most twice as long.  If your design fails when your data size
> doubles, you have problems emacs won't solve.  

I dont think its quite as simple as that…

Consider python wherein
- C is typically 2 orders of magnitude (hundreds of times) faster than python
- the two can cohabit quite closely; eg moving a ordinary python loop to a 
vector numpy operation implicitly moves python to C with corresponding speedup
(and speed-down due to conversion etc)

And so the two versions are not just comparing loop vs loop-loop
but loop₁ vs loop₂ - loop₃
where the ₁₂₃ can vary across {interpreter, bare-metal}
we could have all manner of possibilities of speedup and speed-down

Sure its not nearly as simple to add C to elisp as to python
However it is essentially the same thing: elisp and python are interpreters
sitting on top of C. Which in big-O terms means 1 loop vs 2 constant multiplier
vs bare-metal vs interpretive overhead multiplier

Re: return first element in list with certain property

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 442 bytes --]

Emanuel Berg <moasen@zoho.com> writes:

> See, my intuition was right, seq-find *is*
> better even tho you guys are in denial about
> it :)

The way I see it (I'm completely biased of course), the real advantage
of `seq' is that it provides a complete and consistent sequence
manipulation API (I tried to design it that way at least), and can be
extended to work with other data structures (see stream.el in ELPA for
instance).

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: return first element in list with certain property

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 333 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> If your package package-requires "seq", the package manager should
> install the thing automatically when appropriate.  I'm not sure about
> Emacsen with major version < 24, though.

I have never tried loading `seq' in Emacs < 24, so don't expect this to
work :)

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: return first element in list with certain property

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 245 bytes --]

Emanuel Berg <moasen@zoho.com> writes:

> OK, so is it different in Emacs 25? Or is one
> still supposed to get seq.el from ELPA, only
> with no backport hassle?

Yes, seq.el is included in Emacs since 25.1 (same goes for map.el).

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: return first element in list with certain property

[Emanuel Berg]

Nicolas Petton wrote:

> The way I see it (I'm completely biased of
> course), the real advantage of `seq' is that
> it provides a complete and consistent
> sequence manipulation API (I tried to design
> it that way at least), and can be extended to
> work with other data structures (see
> stream.el in ELPA for instance).

With respect to this particular issue, seq and
`seq-find' is superior to CL and `cl-find-if'.
After that was revealed, the only thing that
made me hesitant about using it was the install
hassle. But now that you say it is included in
vanilla Emacs from version 25, which is right
around the corner, perhaps I should use
it still?

How will this be expressed in the source?
Will plain `require' be enough? There was talk
in another post the package should
"package-require" it so it will be installed
automatically along with the package. But if
there is a function to do this, I can't find
it. And if there is, will it be transparent so
it won't install anything unless necessary?

Or do I have to prompt the current Emacs
version to take different action?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Michael Heerdegen]

Emanuel Berg <moasen@zoho.com> writes:

> How will this be expressed in the source?  Will plain `require' be
> enough?

No.

> There was talk in another post the package should "package-require" it
> so it will be installed automatically along with the package. But if
> there is a function to do this, I can't find it. And if there is, will
> it be transparent so it won't install anything unless necessary?

Sure, it won't.

You declare package dependencies in the package header - see (info
"(elisp) Simple Packages") - that's what I called "package-require".

You maybe want to read the whole (info "(elisp) Packaging").  Everything
is quite simple.


Michael.

Re: return first element in list with certain property

[Emanuel Berg]

Michael Heerdegen wrote:

> You maybe want to read the whole (info
> "(elisp) Packaging"). Everything is
> quite simple.

Oh, no! A whole new section! I still haven't
read the whole one on "Tips and Conventions"...

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[John Mastro]

Emanuel Berg <moasen@zoho.com> wrote:
> With respect to this particular issue, seq and
> `seq-find' is superior to CL and `cl-find-if'.
> After that was revealed, the only thing that
> made me hesitant about using it was the install
> hassle. But now that you say it is included in
> vanilla Emacs from version 25, which is right
> around the corner, perhaps I should use
> it still?

Emacs 25 was released a bit over a year ago, in September 2016 :)

I think it's perfectly reasonable to use seq.el in your package.

        John

Re: return first element in list with certain property

[Robert Thorpe]

John Mastro <john.b.mastro@gmail.com> writes:

> Emanuel Berg <moasen@zoho.com> wrote:
>> With respect to this particular issue, seq and
>> `seq-find' is superior to CL and `cl-find-if'.
>> After that was revealed, the only thing that
>> made me hesitant about using it was the install
>> hassle. But now that you say it is included in
>> vanilla Emacs from version 25, which is right
>> around the corner, perhaps I should use
>> it still?
>
> Emacs 25 was released a bit over a year ago, in September 2016 :)
>
> I think it's perfectly reasonable to use seq.el in your package.

I don't agree, 24 isn't that old.  Perhaps you use Microsoft Windows?

Those of us using *nix derivatives are in a different situation.
Upgrading is risky.  If you use GNU/Linux (or whatever you call it) it
makes sense to stick with one distribution (I use Xubuntu).  It makes
sense not to upgrade too regularly.  Compiling Emacs is a non-starter
because there are too many build options and nobody understands them
except distro builders and the Emacs maintainers.  Unfortunately, that
means not upgrading Emacs.

I use Emacs 25.2 at work on MS Windows.  At home I use Emacs 24.5.  I will
continue to use it until I have to upgrade Ubuntu.

I consider this worthwhile because owning and updating a MS Windows
machine would be much more troublesome and expensive.  That applies
whatever you think about software licensing.  However, for Emacs it
means using older versions.

BR,
Robert Thorpe

Re: return first element in list with certain property

[Alexis]

Robert Thorpe <rt@robertthorpeconsulting.com> writes:

> Compiling Emacs is a non-starter because there are too many 
> build
> options and nobody understands them except distro builders and 
> the
> Emacs maintainers.

As a data point: i use Debian, am neither a distro builder nor an 
Emacs
maintainer, but nevertheless compile Emacs myself. Once the 
development
libraries are installed - and i only need to do so manually once 
per
Debian installation - all i need to do is unpack the Emacs 
tarball, cd
to the unpacked directory, and do the usual:

$ ./configure && make && make install

which, in my experience, Does The Right Thing.


Alexis.

Re: return first element in list with certain property

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sat, Nov 25, 2017 at 03:54:15AM +0000, Robert Thorpe wrote:
> John Mastro <john.b.mastro@gmail.com> writes:
> 
> > Emanuel Berg <moasen@zoho.com> wrote:
> >> With respect to this particular issue, seq and
> >> `seq-find' is superior to CL and `cl-find-if'.
> >> After that was revealed, the only thing that
> >> made me hesitant about using it was the install
> >> hassle. But now that you say it is included in
> >> vanilla Emacs from version 25, which is right
> >> around the corner, perhaps I should use
> >> it still?
> >
> > Emacs 25 was released a bit over a year ago, in September 2016 :)
> >
> > I think it's perfectly reasonable to use seq.el in your package.
> 
> I don't agree, 24 isn't that old.  Perhaps you use Microsoft Windows?
> 
> Those of us using *nix derivatives are in a different situation.
> Upgrading is risky.  If you use GNU/Linux (or whatever you call it) it
> makes sense to stick with one distribution (I use Xubuntu).  It makes
> sense not to upgrade too regularly.  Compiling Emacs is a non-starter
> because there are too many build options and nobody understands them
> except distro builders and the Emacs maintainers.  Unfortunately, that
> means not upgrading Emacs.

[...]

I disagree somewhat. At the moment, Emacs tip is compiling peacefully
in the background (Debian GNU Linux user here). Compiling Emacs has
never been so easy, especially on GNU/Linux.

My strategy is this: There are some applications close to my heart
(Emacs is one :) which I do compile myself (I have a strong opinion
about things, and disagree on some choices made by the distributor).
I try to script everything (e.g. the "configuration" is a script)
and compile often. This keeps the build pipeline "warm".

That said, I agree, somewhat, too: I couldn't do that to all of my
currently installed packages (roughly 100) without going insane.
There I trust blindly my distributor, to whom I'm infinitely grateful
for this incredible job.

Cheers
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEARECAAYFAloZF2EACgkQBcgs9XrR2kZGWACffoOO9KgKFHtbWrIOh7eIUmr5
ItUAn32g+JRiTZkBllNJYkmwb5bmSgQP
=J65L
-----END PGP SIGNATURE-----

Re: return first element in list with certain property

[Eli Zaretskii]

> From: Robert Thorpe <rt@robertthorpeconsulting.com>
> Date: Sat, 25 Nov 2017 03:54:15 +0000
> Cc: help-gnu-emacs@gnu.org
> 
> Compiling Emacs is a non-starter because there are too many build
> options and nobody understands them except distro builders and the
> Emacs maintainers.

??? Just use the defaults (i.e. no options except, perhaps, --prefix),
and you should be fine.  The non-default options indeed need you to
understand them, but they are for corner cases, and generally can be
ignored unless your needs are unusual, e.g. if your Unix box is
32-bit, or your GTK is buggy.

Re: return first element in list with certain property

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sat, Nov 25, 2017 at 09:46:28AM +0200, Eli Zaretskii wrote:
> > From: Robert Thorpe <rt@robertthorpeconsulting.com>
> > Date: Sat, 25 Nov 2017 03:54:15 +0000
> > Cc: help-gnu-emacs@gnu.org
> > 
> > Compiling Emacs is a non-starter because there are too many build
> > options and nobody understands them except distro builders and the
> > Emacs maintainers.
> 
> ??? Just use the defaults (i.e. no options except, perhaps, --prefix),
> and you should be fine [...]

Yes. And even for crazy nuts as me who do care about some options,
it's just as difficult as finding out once and letting a shell
script "remember" the settings (perhaps adjust once a year).

But one has to choose which packages to care about and which ones
to leave to the distributor. Decisions, decisions... :)

Cheers
- -- t
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEARECAAYFAloZI+oACgkQBcgs9XrR2kZTtgCdGC1OjLRt0nwN6h5GnzpwTwE8
kSIAn0e/p5zcF9cdGwTA/iFtWZ2wInhS
=Oxfk
-----END PGP SIGNATURE-----

Re: return first element in list with certain property

[Emanuel Berg]

t wrote:

> I disagree somewhat. At the moment, Emacs tip
> is compiling peacefully in the background
> (Debian GNU Linux user here). Compiling Emacs
> has never been so easy, especially on
> GNU/Linux.
>
> My strategy is this: There are some
> applications close to my heart (Emacs is one
> :) which I do compile myself (I have a strong
> opinion about things, and disagree on some
> choices made by the distributor). I try to
> script everything (e.g. the "configuration"
> is a script) and compile often. This keeps
> the build pipeline "warm".

Yes, it is not difficult to compile Emacs or
any other individual application from source.
If it is then something is wrong. To put the
process (procedure) in a script or shell
function is a good idea, if you didn't get
a script with the tarball. Even so you can
execute that script from your own script or
function :) What's difficult about compiling is
when multiple programs are involved and they
depend on each other in ways that are difficult
for a human to grasp. Luckily that is easy for
a computer to which is the basis for the by now
very successful packet managers.

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[John Mastro]

Robert Thorpe <rt@robertthorpeconsulting.com> wrote:
> John Mastro <john.b.mastro@gmail.com> writes:
> > Emacs 25 was released a bit over a year ago, in September 2016 :)
> >
> > I think it's perfectly reasonable to use seq.el in your package.
>
> I don't agree, 24 isn't that old.  Perhaps you use Microsoft Windows?

I am (un)lucky enough to use all three of GNU/Linux, MacOS, and Windows
on a regular basis.

> Those of us using *nix derivatives are in a different situation.
> Upgrading is risky.  If you use GNU/Linux (or whatever you call it) it
> makes sense to stick with one distribution (I use Xubuntu).  It makes
> sense not to upgrade too regularly.  Compiling Emacs is a non-starter
> because there are too many build options and nobody understands them
> except distro builders and the Emacs maintainers.  Unfortunately, that
> means not upgrading Emacs.

I agree that some users won't be comfortable compiling Emacs (or any
program) themselves. However, I don't agree that "upgrading [Emacs] is
risky", it's "a non-starter", or that "nobody understands [build
options]", especially not for users on GNU/Linux or Unix-like systems in
general.

> I use Emacs 25.2 at work on MS Windows.  At home I use Emacs 24.5.  I will
> continue to use it until I have to upgrade Ubuntu.

FWIW, I build Emacs's master branch (Emacs 27.0.50) on all three
platforms, and I'm neither a distro builder nor an Emacs maintainer.

> I consider this worthwhile because owning and updating a MS Windows
> machine would be much more troublesome and expensive.  That applies
> whatever you think about software licensing.  However, for Emacs it
> means using older versions.

More generally, I want to note that I didn't say "there are no downsides
to using seq.el in place of cl-lib" or "there's no case for supporting
Emacs versions < 25.1". However, particularly for a new package with no
existing users, I do think it's perfectly reasonable to use seq.el and
support only Emacs versions >= 25.1.

        John

Re: return first element in list with certain property

[Emanuel Berg]

John Mastro wrote:

> I do think it's perfectly reasonable to use
> seq.el and support only Emacs versions >=
> 25.1.

So if I do, I don't need to "package-require"
it in the commented package header? It
will be enough with just a `require'?

However since the "package-require" was
supposed to be transparent, and not download
anything unless needed, doesn't that amount to
- if I put it there - it will be installed on
< 25.1, but not installed on version where seq
is part of vanilla Emacs?

Or is this "in theory" only?

> I agree that some users won't be comfortable
> compiling Emacs (or any program) themselves.
> However, I don't agree that "upgrading
> [Emacs] is risky", it's "a non-starter", or
> that "nobody understands [build options]",
> especially not for users on GNU/Linux or
> Unix-like systems in general.

I think the last quote was a way of saying "it
is difficult" - which you and I don't agree on
anyway :)

But as for the build options, what options is
it that are difficult to understand?
They should be documented somewhere if they are
not self-explanatory or conventional enough -
there should be comments in code at the very
least. Try understanding them one by one
instead of grouping them together claiming them
beyond mere users. And if everything fails,
just use the default ones and be a happy Emacs
user ever ever :)

> More generally, I want to note that I didn't
> say "there are no downsides to using seq.el
> in place of cl-lib" or "there's no case for
> supporting Emacs versions < 25.1". However,
> particularly for a new package with no
> existing users

Yes, one :) And not just anyone, either :))

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Michael Heerdegen]

Emanuel Berg <moasen@zoho.com> writes:

> John Mastro wrote:
>
> > I do think it's perfectly reasonable to use seq.el and support only
> > Emacs versions >= 25.1.
>
> So if I do, I don't need to "package-require" it in the commented
> package header? It will be enough with just a `require'?

Yes.

> However since the "package-require" was supposed to be transparent,
> and not download anything unless needed, doesn't that amount to - if I
> put it there - it will be installed on < 25.1, but not installed on
> version where seq is part of vanilla Emacs?

Exactly.  Have a look at the "beacon" package for example.  It depends
on "seq" - see the header.  If you install it in Emacs 24, the "seq"
Elpa package will be installed along with it.  In Emacs 25, only the
"beacon" package itself is installed.  Try it!


Michael.

Re: return first element in list with certain property

[Robert L.]

On 11/19/2017, Philipp Stephani wrote:

> Emanuel Berg <moasen@zoho.com> schrieb am So., 19. Nov. 2017 um 21:44 Uhr:
> 
> > What is considered the right way to return the
> > first element in list that has
> > a certain property?
> > 
> > The best way I've found so far is `cl-some' and
> > then `and'. While I don't consider the
> > "`and' hack" to be detrimental in any way I was
> > curious if there was a complete
> > "hack free" way...
> > 
> 
> cl-find-if


(defun list-find-if (pred xs)
  (while (and (consp xs) (not (funcall pred (car xs))))
    (pop xs))
  (car xs))

-- 
The report card by the American Society of Civil Engineers showed the national
infrastructure a single grade above failure, a step from declining to the point
where everyday things simply stop working the way people expect them to.
http://archive.org/details/nolies

Re: return first element in list with certain property

[Emanuel Berg]

Robert L. wrote:

>> cl-find-if
>
> (defun list-find-if (pred xs)
>   (while (and (consp xs) (not (funcall pred (car xs))))
>     (pop xs))
>   (car xs))

OK, but without having tested it, is there any
reason to favor it to `cl-find-if'?

-- 
underground experts united
http://user.it.uu.se/~embe8573

Re: return first element in list with certain property

[Emanuel Berg]

> OK, but without having tested it, is there
> any reason to favor it to `cl-find-if'?

Now I have tested it and it seems
"list-find-if" is a little faster than
`cl-find-if'!

So good job even tho I will stick to CL
thank you :)

(require 'cl-lib)

(defun list-find-if (pred xs)
  (while (and (consp xs)
              (not (funcall pred (car xs))) )
    (pop xs) )
  (car xs) )

(let*((max-value          1000000)
      (random-list        (create-random-list max-value max-value))
      (bigger-than-random (lambda (e) (> e (random max-value)))) )
  (message "Testing for %s" max-value)
  (message
   "Test list-find-if: %s"
   (measure-time (list-find-if bigger-than-random random-list)) )
  (message
   "Test cl-find-if: %s"
   (measure-time (cl-find-if   bigger-than-random random-list)) )
  )

"create-random-list" and "measure-time" here:

    http://user.it.uu.se/~embe8573/emacs-init/measure.el

-- 
underground experts united
http://user.it.uu.se/~embe8573