Re: return first element in list with certain property

[Rusi <rustompmody@gmail.com>]

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