Re: passing predicates to lowerBound, or alternatively, how lazy is map?

[John Colvin via Digitalmars-d-learn]

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