[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: return first element in list with certain property
From: |
Rusi |
Subject: |
Re: return first element in list with certain property |
Date: |
Wed, 22 Nov 2017 06:52:20 -0800 (PST) |
User-agent: |
G2/1.0 |
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, (continued)
- 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
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/21
- RE: return first element in list with certain property, Drew Adams, 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, Drew Adams, 2017/11/21
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/21
- Message not available
- Re: return first element in list with certain property, James K. Lowden, 2017/11/21
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/22
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/22
- Re: return first element in list with certain property,
Rusi <=
- Re: return first element in list with certain property, Nicolas Petton, 2017/11/22
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/22
- Re: return first element in list with certain property, Michael Heerdegen, 2017/11/22
- Re: return first element in list with certain property, Emanuel Berg, 2017/11/22
- Re: return first element in list with certain property, John Mastro, 2017/11/24
- Re: return first element in list with certain property, Robert Thorpe, 2017/11/24
- Re: return first element in list with certain property, Alexis, 2017/11/24
- Re: return first element in list with certain property, tomas, 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, Eli Zaretskii, 2017/11/25