On 04/07/2019 08:41 AM, Robert M. Münch wrote:
> I have an AA int[ulong] and would like to traverse the AA from biggest
> to smallest by value. Is there an elegant way to do this?
Because associative array is a data structure to use when the order is
not important, it comes down to getting the values and then sorting.
Since there is already a .values that returns a copy of the values, I
would just sort that one:
auto arr = aa.values;
sort(arr);
use(arr);
I think that method might be faster than others because .values is
provided by the AA implementation but I shouldn't say that without
testing. :) So, with dmd v2.085.0, .values is 4 times faster than .byValues:
import std.algorithm;
import std.stdio;
import std.array;
import std.range;
import std.typecons;
import std.format;
enum aaElementCount = 100_000;
enum testCount = 100;
ulong expectedResult;
// So that the whole operation is not optimized out
void use(int[] aa) {
const result = aa.sum;
if (expectedResult == 0) {
expectedResult = result;
}
// Make sure that all methods produce the same result
assert(expectedResult != 0);
assert(result == expectedResult, format!"%s != %s"(result,
expectedResult));
}
void main() {
auto aa = aaElementCount.iota.map!(i => tuple(i, i)).assocArray();
import std.datetime.stopwatch;
auto measurements = benchmark!(
{
auto arr = aa.byValue.array;
// sort(arr);
use(arr);
},
{
auto arr = aa.values;
// sort(arr);
use(arr);
},
)(testCount);
writefln("%(%s\n%)", measurements);
}
450 ms, 424 μs, and 8 hnsecs <-- .byValue.array
108 ms, 124 μs, and 6 hnsecs <-- .values
Of course the difference is much less when we comment-in the sort() lines.
Ali
