www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorting routines

reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Anyone have a sort routine that can operate simultaneously on multiple 
arrays of data?

It's basically a lexical sort kind of thing, but all the keys and values 
are in different arrays:
int[] key1;
int[] key2;
ValueT1[] values;
ValueT2[] other_values;

Datum i is made up of (key1[i],key2[i],values[i],other_values[i]).

But they're all stored in separate arrays rather than interleaved in a 
struct.

The goal is to avoid copying the whole mess to an interleaved array in 
order to sort it, and then copying it back to separate arrays.

--bb
Mar 06 2008
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Bill,

 Anyone have a sort routine that can operate simultaneously on multiple
 arrays of data?
 
 It's basically a lexical sort kind of thing, but all the keys and
 values
 are in different arrays:
 int[] key1;
 int[] key2;
 ValueT1[] values;
 ValueT2[] other_values;
 Datum i is made up of (key1[i],key2[i],values[i],other_values[i]).
 
 But they're all stored in separate arrays rather than interleaved in a
 struct.
 
 The goal is to avoid copying the whole mess to an interleaved array in
 order to sort it, and then copying it back to separate arrays.
 
 --bb
 

I don't known of one but... This is ugly... make struct that has just a pointer to the key and an int. set the opCmp to chain to the key and then fill an array with them referencing the keys. Then fill the ints with 0 to whatever. When the thing is sorted you have the index map. from there you can get fancy and do an in place reorder (double yuck) or copy each array and move the items back into the correct cells (or if you don't care, do the reorder on the way out and swap in the new array for the old). How this will compare to a real multi-array sort will depend on a lot of things.
Mar 06 2008
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
BCS wrote:
 Reply to Bill,
 
 Anyone have a sort routine that can operate simultaneously on multiple
 arrays of data?

 It's basically a lexical sort kind of thing, but all the keys and
 values
 are in different arrays:
 int[] key1;
 int[] key2;
 ValueT1[] values;
 ValueT2[] other_values;
 Datum i is made up of (key1[i],key2[i],values[i],other_values[i]).

 But they're all stored in separate arrays rather than interleaved in a
 struct.

 The goal is to avoid copying the whole mess to an interleaved array in
 order to sort it, and then copying it back to separate arrays.

 --bb

I don't known of one but... This is ugly... make struct that has just a pointer to the key and an int. set the opCmp to chain to the key and then fill an array with them referencing the keys. Then fill the ints with 0 to whatever. When the thing is sorted you have the index map. from there you can get fancy and do an in place reorder (double yuck) or copy each array and move the items back into the correct cells (or if you don't care, do the reorder on the way out and swap in the new array for the old). How this will compare to a real multi-array sort will depend on a lot of things.

Hmm. Oh well. I don't really want to have to allocate a whole separate dummy array for indices, but that does seem to be the only way with typcial sort routines. I just went the brute-force way of modifying Oskar's sort routine to handle the case I need. --bb
Mar 06 2008
prev sibling parent Jascha Wetzel <firstname mainia.de> writes:
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Bill Baxter wrote:
 Anyone have a sort routine that can operate simultaneously on multiple 
 arrays of data?
 
 It's basically a lexical sort kind of thing, but all the keys and values 
 are in different arrays:
 int[] key1;
 int[] key2;
 ValueT1[] values;
 ValueT2[] other_values;
 
 Datum i is made up of (key1[i],key2[i],values[i],other_values[i]).
 
 But they're all stored in separate arrays rather than interleaved in a 
 struct.
 
 The goal is to avoid copying the whole mess to an interleaved array in 
 order to sort it, and then copying it back to separate arrays.
 
 --bb

i thought that should be easy with tuple parameters, but something that i think is a bug stopped my litte test. see the attachment. in line 11 the type of b is char[][] (as expected), but using it as such gives an error. bummer...
Mar 07 2008