View mode: basic / threaded / horizontal-split · Log in · Help
August 20, 2004
sorting associative arrays by value?
This has probably been asked before, but I couldn't find anything on it in the
main documentation.

Basically, I am looking for a way to sort an associative array by value, and not
by key. In your wordcount example, you sort the keys and use that to print out
the list of words and their frequency. Basically, I want to modify this to order
the printout by frequency (obviously I don't just want to do this in the
example, but this is just an illustration <g>).

Doing a foreach on array.values.sort gives you the sorted array of values, but
without any way that I can see to get the key value for each of those elements.
Making a copy of the array and switching the value/keys would work, but only in
cases where there were new duplicate values..

Is there something I'm missing in the syntax to achieve this, or would I have to
write such a sorting algorithm myself?

Thanks in advance.
August 21, 2004
Re: sorting associative arrays by value?
niall wrote:

> This has probably been asked before, but I couldn't find anything on it in
> the main documentation.
> 
> Basically, I am looking for a way to sort an associative array by value,
> and not by key. In your wordcount example, you sort the keys and use that
> to print out the list of words and their frequency. Basically, I want to
> modify this to order the printout by frequency (obviously I don't just
> want to do this in the example, but this is just an illustration <g>).
> 
> Doing a foreach on array.values.sort gives you the sorted array of values,
> but without any way that I can see to get the key value for each of those
> elements. Making a copy of the array and switching the value/keys would
> work, but only in cases where there were new duplicate values..
> 
> Is there something I'm missing in the syntax to achieve this, or would I
> have to write such a sorting algorithm myself?
> 
> Thanks in advance.

One way, with keys of type A and values of type B
B[A] orig;
... fill orig ...
B[] sorted_vals = orig.values.sort;
A[][B] inverse;
foreach(A key, B val; orig) // construct the inverse
 inverse[val] ~= key;
foreach(B val; sorted_vals) {
 A[] keys_for_val = inverse[val];
 ... do whatever you want with the keys_for_val ...
}

A more efficient way to do it is to use a SortedAA from MinTL so that you
don't have to sort the array of values as a separate step - they get sorted
during insertion. 

-Ben
August 21, 2004
Re: sorting associative arrays by value?
Ben Hinkle wrote:
> One way, with keys of type A and values of type B
> B[A] orig;
> ... fill orig ...
> B[] sorted_vals = orig.values.sort;
> A[][B] inverse;
> foreach(A key, B val; orig) // construct the inverse
>   inverse[val] ~= key;
> foreach(B val; sorted_vals) {
>   A[] keys_for_val = inverse[val];
>   ... do whatever you want with the keys_for_val ...
> }

That's a nice solution, I hadn't thought of concatenating the keys for 
nonunique values :)

> 
> A more efficient way to do it is to use a SortedAA from MinTL so that you
> don't have to sort the array of values as a separate step - they get sorted
> during insertion. 
> 
> -Ben

I think I'll try the MinTL way, since I'm quite a fan of the STL in C++.

I wonder if the D specification in future might extend the sort property 
 for AAs in order to specify sorting by key or value, since it's quite 
a common operation to want to do on associative arrays?

Thanks for your help -- I'm only just starting to experiment with D, but 
I really like how much more logical and intuitive the language is so far  :)
August 21, 2004
Re: sorting associative arrays by value?
> I wonder if the D specification in future might extend the sort property
>   for AAs in order to specify sorting by key or value, since it's quite
> a common operation to want to do on associative arrays?

Hmm. AA's don't have a sort property. The "keys" property returns a dynamic
array of all the keys and you can sort that. Similarly the "values"
property returns a dynamic array of values. But those arrays contains
copies of the data in the AA - so sorting them will have no effect on the
AA.

> Thanks for your help -- I'm only just starting to experiment with D, but
> I really like how much more logical and intuitive the language is so far 
> :)

me too - hope you enjoy D!
Top | Discussion index | About this forum | D home