www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Short-circuit range counting algorithm?

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
parent reply Seb <seb wilzba.ch> writes:
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
Mar 16 2018
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
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

-Steve
Mar 16 2018
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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.
Mar 16 2018
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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:

 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.


Noice, thanks for the correx all.
Mar 17 2018
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
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.


 T


I'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