Iterate/sort associative array by value?

[Ali Çehreli]

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