in reply to sort performance

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;

[download]
(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.)

Replies are listed 'Best First'.
RE: Re (tilly) 1: sort performance
by runrig (Abbot) on Sep 12, 2000 at 04:45 UTC
    The 'Schwartzian Transform' is for expensive operations.
    A hash lookup is not an expensive operation, so just do a plain sort.
[reply]
      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);

      [download]
      Believe it or not, stupid is several times faster for me than schwartz. IMO there is simply no possible good reason for that!
[reply]
[d/l]

        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  ];

        [download]
                - tye (but my friends call me "Tye")
[reply]
[d/l]
[select]
        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.)

[reply]

In Section Seekers of Perl Wisdom