Short-circuit range counting algorithm?

[H. S. Teoh]

On Fri, Mar 16, 2018 at 02:58:36PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
> On 3/16/18 2:07 PM, Seb wrote:
> > On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:
> > > On 3/16/18 1:41 PM, H. S. Teoh wrote:
> > > > Given a forward range r, I want to test whether it has exactly n
> > > > elements that satisfy some given predicate pred.  Is it possible
> > > > to do this using current Phobos algorithms such that it does not
> > > > traverse more members of the range than necessary?
> > > > 
> > > > The naïve solution `r.count!pred == n` walks the entire range,
> > > > even though it may already have seen n+1 elements that satisfies
> > > > pred, and therefore should already know that the answer must be
> > > > false.
> > > 
> > > r.count!pred.walkLength(n) == n
> > 
> > Shouldn't this be using filter (count is eager)?
> > 
> > r.filter!pred.walkLength(n) == n
> 
> r.filter!pred.walkLength(n + 1) == n
[...]

Aha, so the trick is the 2-argument overload of walkLength.  That's what
I was looking for.  Thanks!

And yes, it should be .walkLength(n+1) because otherwise you don't know
if the actual count is >n.


T

-- 
Don't drink and derive. Alcohol and algebra don't mix.