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
