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

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)();

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

>
> 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.

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.

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

>
> 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?

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.

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.

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