A few range questions

[Ali Çehreli via Digitalmars-d-learn]

On 01/05/2016 01:48 PM, Charles Smith wrote:
 > On Tuesday, 5 January 2016 at 19:42:42 UTC, Ali Çehreli wrote:

 >>     // Now they get their own arrays:
 >>     auto benchmarks = benchmark!(() => algorithmSort(arr.dup),
 >>                                  () => countingSort(arr.dup))(1);
 >>
 >
 > I'm not sure what this explicitly is doing... Are you defining an
 > anonymous function? If so, that seems really useful.

Yes. Since benchmark() expects no-parameter functions, that's a useful 
way of testing functions that take parameters.

However, I should have created the arrays before calling benchmark(). 
Otherwise, the timings include .dup as well:

     auto asArr = arr.dup;
     auto csArr = arr.dup;

     auto benchmarks = benchmark!(() => algorithmSort(asArr),
                                  () => countingSort(csArr))(10);

 >> I think .joiner is what you're looking for.
 > I was searching the terms `concat` and `flatten ` when I was
 > looking for this.

Yep, I always start searching for 'flatten' and then remember joiner. :p

 > That said, I don't think the example for `chain` should compile then.

That worked because chain() received just a single range (of ranges), in 
which case it had no effect.

 >> My results with -O -inline -noboundscheck:
 >>
 >> Algorithm's Sort: 76 ms, 910 μs, and 8 hnsecs
 >> Counting Sort   : 21 ms, 563 μs, and 9 hnsecs

 > Awesome

I am amazed! :) countingSort() beats algorithmSort() almost always. :) 
Here is the final version of the program with 10 million elements and 4 
million values (array that are so large cannot be allocated on the stack 
for me; so, I used new):

enum elementCount = 10_000_000;
enum valueCount = 4_000_000;

void main() {
     import std.conv : to;
     import std.datetime;
     import std.random;
     import std.stdio;

     auto arr = new int[elementCount];

     for(int i; i < arr.length; ++i)
         arr[i] = uniform(0, valueCount);

     auto asArr = arr.dup;
     auto csArr = arr.dup;

     // Now they get their own arrays:
     auto benchmarks = benchmark!(() => algorithmSort(asArr),
                                  () => countingSort(csArr))(10);

     writeln("Algorithm's Sort: ", to!Duration(benchmarks[0]));
     writeln("Counting Sort   : ", to!Duration(benchmarks[1]));
}

auto algorithmSort(int[] arr) {
     import std.algorithm : sort, sum;

     arr.sort();
     return arr.sum;
}

auto countingSort(int[] arr) {
     import std.algorithm : count, map, joiner, sum, each;
     import std.range : array, repeat, enumerate;

     auto hist = new uint[valueCount];
     arr.each!(a => ++hist[a]);

     auto result = hist[].enumerate.map!(t => t[0].repeat(t[1])).joiner;
     return result.sum;
}

Now they are comparable:

Algorithm's Sort: 3 secs, 881 ms, 146 μs, and 1 hnsec
Counting Sort   : 3 secs, 990 ms, 315 μs, and 4 hnsecs

Ali