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