Re (tilly) 1: sort performance

[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!

[tye]

I suspect that the optimizer is just removing the whole $foo bit from "stupid" for you.

I was wondering if $a->[1] would be much faster than $hash{$a}{this}. I didn't think it would be by a big enough factor.

If you want raw speed here, create a side array for comparison and sort a list of indices:

my @list= keys %hash;
my @sort= map { $hash{$_}{this} } @list;
my @sorted= @list[
    sort { $sort[$a] cmp $sort[$b] } 0..$#sort  ];

        - tye (but my friends call me "Tye")

[tilly]

When faced with the ridiculous, look for the obvious. If you change all three to use the same kind of sort, Schwartz runs faster than the other two.

*sigh*

(Stupid user tricks.)