www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - passing predicates to lowerBound, or alternatively, how lazy is map?

reply "Andrew Brown" <aabrown24 hotmail.com> writes:
Hi there,

The problem this question is about is now solved, by writing my 
own binary search algorithm, but I'd like to ask it anyway as I 
think I could learn a lot from the answers.

The problem was, given an array of numbers, double[] numbers, and 
an ordering from makeIndex size_t[] order, I want to count how 
many numbers are less than a number N. The obvious way would be 
to use lowerBound from std.range, but I can't work out how to 
pass it a predicate like "numbers[a] < b". Could someone explain 
the template:

(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value) if 
(isTwoWayCompatible!(predFun, ElementType!Range, V));

The alternative way I thought to do it was to combine map with 
lowerBound, i.e.:

map!(a => numbers[a])(order).assumeSorted
                             .lowerBound(N)
                             .length

My question about this is how lazy is map? Will it work on every 
value of order and then pass it to lowerBound, or could it work 
to evaluate only those values asked by lowerBound? I guess 
probably not, but could a function be composed that worked in 
this way?

Thank you very much

Andrew
Jun 11 2014
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 11 June 2014 at 11:22:08 UTC, Andrew Brown wrote:

 Hi there,

 The problem this question is about is now solved, by writing my 
 own binary search algorithm, but I'd like to ask it anyway as I 
 think I could learn a lot from the answers.

 The problem was, given an array of numbers, double[] numbers, 
 and an ordering from makeIndex size_t[] order, I want to count 
 how many numbers are less than a number N. The obvious way 
 would be to use lowerBound from std.range, but I can't work out 
 how to pass it a predicate like "numbers[a] < b". Could someone 
 explain the template:

 (SearchPolicy sp = SearchPolicy.binarySearch, V)(V value) if 
 (isTwoWayCompatible!(predFun, ElementType!Range, V));

 The alternative way I thought to do it was to combine map with 
 lowerBound, i.e.:

 map!(a => numbers[a])(order).assumeSorted
                             .lowerBound(N)
                             .length

 My question about this is how lazy is map? Will it work on 
 every value of order and then pass it to lowerBound, or could 
 it work to evaluate only those values asked by lowerBound? I 
 guess probably not, but could a function be composed that 
 worked in this way?

 Thank you very much

 Andrew


map is fully lazy.

However, if you've already got the sorted indices in `order`, I 
would do this:

auto numLessThanN = numbers.indexed(order).countUntil!((x) => x 

= N)();
Jun 11 2014
next sibling parent reply "Andrew Brown" <aabrown24 hotmail.com> writes:
 My question about this is how lazy is map? Will it work on 
 every value of order and then pass it to lowerBound, or could 
 it work to evaluate only those values asked by lowerBound? I 
 guess probably not, but could a function be composed that 
 worked in this way?

 Thank you very much

 Andrew


 map is fully lazy.

 However, if you've already got the sorted indices in `order`, I 
 would do this:

 auto numLessThanN = numbers.indexed(order).countUntil!((x) => x

= N)();




Thanks for the reply, I'm going to have a lot of numbers though. 
I guess compared to the time it will take me to sort them, it 
makes no difference, but is it right that countUntil will take 
linear time? If I can figure out lowerBound, then I have my 
answer in log(n) time?

Best

Andrew
Jun 11 2014
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 11 June 2014 at 11:38:07 UTC, Andrew Brown wrote:

 My question about this is how lazy is map? Will it work on 
 every value of order and then pass it to lowerBound, or could 
 it work to evaluate only those values asked by lowerBound? I 
 guess probably not, but could a function be composed that 
 worked in this way?

 Thank you very much

 Andrew


 map is fully lazy.

 However, if you've already got the sorted indices in `order`, 
 I would do this:

 auto numLessThanN = numbers.indexed(order).countUntil!((x) => x

= N)();




 Thanks for the reply, I'm going to have a lot of numbers 
 though. I guess compared to the time it will take me to sort 
 them, it makes no difference, but is it right that countUntil 
 will take linear time? If I can figure out lowerBound, then I 
 have my answer in log(n) time?

 Best

 Andrew


You are correct. assumeSorted and lowerBound will provide better 
time complexity than countUntil
Jun 11 2014
parent reply "Andrew Brown" <aabrown24 hotmail.com> writes:
 You are correct. assumeSorted and lowerBound will provide 
 better time complexity than countUntil


I'm sorry, one final question because I think I'm close to 
understanding. Map produces a forward range (lazily) but not a 
random access range? Therefore, lowerBound will move along this 
range until the pred is not true? This means it would be better 
to do:

numbers.indexed(order).assumeSorted.lowerBound

than:

map(a => numbers[a])(order).assumeSorted.lowerBound

as the lowerBound will be faster on a random access range as 
produced by indexed?
Jun 11 2014
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 11 June 2014 at 13:20:37 UTC, Andrew Brown wrote:

 You are correct. assumeSorted and lowerBound will provide 
 better time complexity than countUntil


 I'm sorry, one final question because I think I'm close to 
 understanding. Map produces a forward range (lazily) but not a 
 random access range? Therefore, lowerBound will move along this 
 range until the pred is not true? This means it would be better 
 to do:

 numbers.indexed(order).assumeSorted.lowerBound

 than:

 map(a => numbers[a])(order).assumeSorted.lowerBound

 as the lowerBound will be faster on a random access range as 
 produced by indexed?


map preserves the random access capabilities of it's source. An 
array is random access, therefore map applied to an array is also 
random access.

There isn't any practical difference between indices.map!((i) => 
src[i])() and src.indexed(indices) that I know of.
Jun 11 2014
parent reply "Andrew Brown" <aabrown24 hotmail.com> writes:
On Wednesday, 11 June 2014 at 13:25:03 UTC, John Colvin wrote:

 On Wednesday, 11 June 2014 at 13:20:37 UTC, Andrew Brown wrote:

 You are correct. assumeSorted and lowerBound will provide 
 better time complexity than countUntil


 I'm sorry, one final question because I think I'm close to 
 understanding. Map produces a forward range (lazily) but not a 
 random access range? Therefore, lowerBound will move along 
 this range until the pred is not true? This means it would be 
 better to do:

 numbers.indexed(order).assumeSorted.lowerBound

 than:

 map(a => numbers[a])(order).assumeSorted.lowerBound

 as the lowerBound will be faster on a random access range as 
 produced by indexed?


 map preserves the random access capabilities of it's source. An 
 array is random access, therefore map applied to an array is 
 also random access.

 There isn't any practical difference between indices.map!((i) 
 => src[i])() and src.indexed(indices) that I know of.


That's great, thank you very much for taking the time to answer.
Jun 11 2014
parent "Andrew Brown" <aabrown24 hotmail.com> writes:
So I was hoping for a learning experience, and I got it. With a 
little playing around, looking at phobos, and TDPL, I think I've 
figured out how lowerBound gets its predicate. It learns it from 
assumeSorted. So I can do this:

order.assumeSorted!((a, b) => number[a] < number[b])
      .lowerBound(order[4])

and I'll retrieve the indices of the 4 smallest numbers. Not 
useful for my current purposes, but is getting me closer to 
figuring out how higher level functions and ranges work.

Thanks

Andrew
Jun 11 2014
prev sibling parent reply "Andrew Brown" <aabrown24 hotmail.com> writes:
 map is fully lazy.

 However, if you've already got the sorted indices in `order`, I 
 would do this:

 auto numLessThanN = numbers.indexed(order).countUntil!((x) => x

= N)();




That indexed command is perfect though, does the trick, thank you 
very much.
Jun 11 2014
parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 11 June 2014 at 11:50:36 UTC, Andrew Brown wrote:

 map is fully lazy.

 However, if you've already got the sorted indices in `order`, 
 I would do this:

 auto numLessThanN = numbers.indexed(order).countUntil!((x) => x

= N)();




 That indexed command is perfect though, does the trick, thank 
 you very much.


For future reference: map applies its predicate in `front`, 
meaning that

a) It is completely lazy, you only pay for elements you actually 
access.

b) Unless the optimiser is smart and caches the result for you, 
you pay every time you call `front`, even if you haven't called 
`popFront` in between.
Jun 11 2014