Short-circuit range counting algorithm?

Seb seb at wilzba.ch
Fri Mar 16 18:07:54 UTC 2018


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


More information about the Digitalmars-d mailing list