## digitalmars.D - Short-circuit range counting algorithm?

- H. S. Teoh (10/10) Mar 16 2018 Given a forward range r, I want to test whether it has exactly n
- Andrei Alexandrescu (2/10) Mar 16 2018 r.count!pred.walkLength(n) == n
- Seb (4/19) Mar 16 2018 Shouldn't this be using filter (count is eager)?
- Steven Schveighoffer (3/19) Mar 16 2018 r.filter!pred.walkLength(n + 1) == n
- H. S. Teoh (9/29) Mar 16 2018 [...]
- Andrei Alexandrescu (2/30) Mar 17 2018 Noice, thanks for the correx all.
- =?UTF-8?B?Tm9yZGzDtnc=?= (4/13) Mar 16 2018 I've implemented these by hand as special cases of count named

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. T -- The early bird gets the worm. Moral: ewww...

Mar 16 2018

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

Mar 16 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:Shouldn't this be using filter (count is eager)? r.filter!pred.walkLength(n) == nGiven 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

Mar 16 2018

On 3/16/18 2:07 PM, Seb wrote:On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:r.filter!pred.walkLength(n + 1) == n -SteveOn 3/16/18 1:41 PM, H. S. Teoh wrote:Shouldn't this be using filter (count is eager)? r.filter!pred.walkLength(n) == nGiven 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

Mar 16 2018

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:[...] 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.On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:r.filter!pred.walkLength(n + 1) == nOn 3/16/18 1:41 PM, H. S. Teoh wrote:Shouldn't this be using filter (count is eager)? r.filter!pred.walkLength(n) == nGiven 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

Mar 16 2018

On 03/16/2018 03:10 PM, H. S. Teoh wrote:On Fri, Mar 16, 2018 at 02:58:36PM -0400, Steven Schveighoffer via Digitalmars-d wrote:Noice, thanks for the correx all.On 3/16/18 2:07 PM, Seb wrote:[...] 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.On Friday, 16 March 2018 at 17:50:37 UTC, Andrei Alexandrescu wrote:r.filter!pred.walkLength(n + 1) == nOn 3/16/18 1:41 PM, H. S. Teoh wrote:Shouldn't this be using filter (count is eager)? r.filter!pred.walkLength(n) == nGiven 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

Mar 17 2018

On Friday, 16 March 2018 at 17:41:22 UTC, 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. TI've implemented these by hand as special cases of count named countsExactly, countsAtLeast, countsAtMost beginning at https://github.com/nordlow/phobos-next/blob/3682da65ecb8497946379b41d8027b8292c635a1/src/algorithm_ex.d#L1941

Mar 16 2018