sort performance

[le]

I have a big hash of hashes that looks like this:

%hash = (
    foo => {
        this => '...',
        that => '...',
        here => '...',
        there => '...'
        },
    bar => {
        this => '...',
        that => '...',
        here => '...',
        there => '...'
        }
);

What would be the most performant way to sort keys %hash on the values of 'this', for example?

Currently, I do it with

for (sort { $hash{$a}->{this} <=> $hash{$b}->{this} } keys %hash)

Is there anything faster/better?

[Adam]

my @sortedkeys = sort { $hash{$a}->{this} cmp $hash{$b}->{this} } keys
+ %hash

You don't need the foreach loop, otherwise your method is fine (that's how I always do it.)

Update: Oh, my mistake... I see that @sortedkeys is the array for the foreach loop. So you are doing fine, although for fun we should try to come up with a bunch of methods and then benchmark them.

[tilly]

You could avoid repeated double-lookups with a Schwartzian sort:

my @sorted_keys = map {$_->[0]}
    sort {$a->[1] cmp $b->[1]}
    map {[$_, $hash{$_}{this}]} keys %hash;

(Read it bottom to top and it will make more sense.)

This is more memory intensive, but doing the double lookup in the sort block means that it happens O(n * log(n)) times. Doing it in a map means it only happens n times. (Where n is the number of keys.)

[runrig]

The 'Schwartzian Transform' is for expensive operations.
A hash lookup is not an expensive operation, so just do a plain sort.

[tilly]

You are right. I just benchmarked it. The overhead of the maps far outweighs the cost of the sort. In fact it is so slow I will have to ask p5p about it. Here is my test:

use strict;
use Benchmark;
use vars qw(%hash %test);

for (1..1000) {
    $hash{"key$_"}{this} = "num$_";
}

%test = (
    schwartz => sub {
        my @sorted = map $_->[0],
            sort {$a->[1] cmp $b->[1]}
            map [$_, $hash{$_}{this}], keys %hash; 
    },
    straight => sub {
        my @sorted = sort
            { $hash{$a}{this} <=> $hash{$b}{this} }
            keys %hash;
    },
    stupid => sub {
        my @sorted = sort
            {
                my $foo = [$a, $hash{$a}{this}];
                $hash{$a}{this} <=> $hash{$b}{this}
            } keys %hash;
    },
);

timethese (-1, \%test);

Believe it or not, stupid is several times faster for me than schwartz. IMO there is simply no possible good reason for that!