www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - sorting associative arrays by value?

reply niall <niall_member pathlink.com> writes:
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.
Aug 20 2004
parent reply Ben Hinkle <bhinkle4 juno.com> writes:
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
Aug 20 2004
parent reply Niall FitzGibbon <nfitzgibbon blueyonder.co.uk> writes:
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  :)
Aug 20 2004
parent Ben Hinkle <bhinkle4 juno.com> writes:
 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!
Aug 20 2004