Re: Sorting keys of hash table by values

[kyle]

Just reverse sort:

@sortedKeys = reverse sort { $h{$a} <=> $h{$b} } keys %h;

[rjray]

Bad. reverse means extra operations and making a second list that is the same size as the original.

The first reply is the best, as it does not involve any extra operations.

[kyle]

I thought you might say that (and by "you", I mean "somebody").

use Benchmark  qw( cmpthese );
use List::Util qw( shuffle );

my @set = shuffle 1 .. 1_000_000;

cmpthese( 100,
          { 'sort' => sub { my @x = sort { $b <=> $a } @set; return; }
+,
            'rsort' => sub { my @x = reverse sort { $a <=> $b } @set; 
+return; },
       } );
__END__
        Rate  sort rsort
sort  1.01/s    --   -2%
rsort 1.03/s    2%    --

(As I recall, 2% is within the margin of error for Benchmark.)

In perl (the implementation of Perl), there's a special case for reverse sort so that it doesn't have the performance penalty you might otherwise expect it to have. That being the case, the main difference between reverse sort { $a cmp $b } and sort { $b cmp $a } is how they read to the programmer. I think that it's far more obvious what's going on when you reverse sort especially as the expressions involved become more complicated. It could be pretty easy to lose the $a and $b in a big block. Even if it were not optimized, I think you'd have to have a pretty long list before the performance penalty outweighs the maintainability benefit.

This also means there's no performance penalty for reverse sort { $b <=> $a }, but that's just rude.

[lidden]

Did you try it?
I thought that too but testing samtregar and kyles versions took the same time. Ikegamis version is about 6% slower.

[rjray]

How did you test it? What size(s) of hash tables? How many iterations? Particularly if the hash table is small, the differences could be swallowed up by variations in the O/S CPU scheduling and other tasks running at the same time.