Sorting by Array values, obtaining indices

PetaMem has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

consider a given, very numeric, hash:

my %hash = ( 0 => 3,
             1 => 7,
             2 => 5,
             3 => 0,
             4 => 2,
           );
[download]

Now - no problem to sort this hash by values and obtain a list containing the new ordering of the keys (in the example above, that'd be: 3,4,0,2,1 if ascending sort)

Now such a hash is pretty trivial and also space consuming. I'd like to have the values of the hash in some array, because there are only numerical indices, no index spaces etc. So given an array:

my @vals = qw(3 7 5 0 2);
[download]

how do I get from this the array @idx = qw(3,4,0,2,1)? I'd like to avoid to go via a hash. Thanks for any enlightment.

Bye
PetaMem All Perl: MT, NLP, NLU

Comment on Sorting by Array values, obtaining indices Select or Download Code

Replies are listed 'Best First'.
Re: Sorting by Array values, obtaining indices by BrowserUk (Patriarch) on Jun 27, 2005 at 16:18 UTC
Sort the indices by the values of the array elements those indices index: `my @vals = qw(3 7 5 0 2); my @index = sort{ $vals[ $a ] <=> $vals[ $b ] } 0 .. $#vals; print @index; 3 4 0 2 1` [download] Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.	[reply] [d/l]
Re: Sorting by Array values, obtaining indices by Limbic~Region (Chancellor) on Jun 27, 2005 at 16:19 UTC
PetaMem, Sort the indices but use the values as the test. `my @idx = sort {$val[$a] <=> $val[$b]} 0 .. $#vals` [download] Though I question the argument that hashes take up more space as a legitimate reason not to use them? Cheers - L~R	[reply] [d/l]
Re^2: Sorting by Array values, obtaining indices by PetaMem (Priest) on Jun 27, 2005 at 16:36 UTC
Though I question the argument that hashes take up more space as a legitimate reason not to use them? Do you? `use strict; use Devel::Size qw(total_size); my %hash = ( 0 => 3, 1 => 7, 2 => 5, 3 => 0, 4 => 2, ); my @vals = qw(3 7 5 0 2); print 'T1: ', total_size(\%hash),"\n"; print 'T2: ', total_size(\@vals),"\n";` [download] 30% less space for the array, same access speed. There need to be as many of these data structures in memory as possible. qed Bye PetaMem All Perl: MT, NLP, NLU	[reply] [d/l]
Re^3: Sorting by Array values, obtaining indices by waswas-fng (Curate) on Jun 27, 2005 at 17:08 UTC
And hashes can be more efficient if there are holes in the index. `use strict; use Devel::Size qw(total_size); my %hash = ( 0 => 3, 1 => 7, 2 => 5, 3 => 0, 20202 => 2, ); my @vals = qw(3 7 5 0); $vals[20202] = 2; print 'T1: ', total_size(\%hash),"\n"; print 'T2: ', total_size(\@vals),"\n"; [waswas:/var/tmp] waswas% perl hah T1: 291 T2: 131228` [download] -Waswas	[reply] [d/l]
Re^3: Sorting by Array values, obtaining indices by Limbic~Region (Chancellor) on Jun 27, 2005 at 16:44 UTC
PetaMem, Yeah. I know they take up more space and can be slower than arrays WRT accessing. The work involved in making an array work when a hash makes natural sense almost always outweighs the benefit gained by not using the hash. Let me put it another way. When you need to access something by key then a hash is almost always the way to go. I feel that with the amount of information originally given, it was not unexpected to question the motives of using an array over a hash. I am not saying there is never a reason not to use a hash - it is just good to get a sanity check first. Cheers - L~R	[reply]
Re: Sorting by Array values, obtaining indices by salva (Canon) on Jun 27, 2005 at 19:01 UTC
`use Sort::Key qw(nsortkey); my @vals = (3, 7, 5, 0, 2); my @idx = nkeysort { $vals[$_] } 0..$#vals;` [download] BTW, creating the list of numbers with qw uses much more memory than if you create then as integers (or floats) on the first place. On a 32 bit machine, an integer value uses 16 bytes, a float 20 and a dual string&number value around 36.	[reply] [d/l]
Re: Sorting by Array values, obtaining indices by tlm (Prior) on Jun 27, 2005 at 16:26 UTC
`my @idx = map $_->[1], sort { $a->[0] <=> $b->[0] } map [$vals[$_], $_], 0..$# +vals;` [download] D'oh. the lowliest monk	[reply] [d/l] [select]
Re: Sorting by Array values, obtaining indices by ambrus (Abbot) on Jun 27, 2005 at 16:37 UTC
Try something like this: `@vals = @hash{0 .. 4};` [download]	[reply] [d/l]