Welcome to the Monastery PerlMonks

### Re (tilly) 1: sort performance

by tilly (Archbishop)
 on Sep 12, 2000 at 04:01 UTC Need Help??

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.)

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

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")
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.)

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://32028]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others pondering the Monastery: (6)
As of 2024-09-18 22:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The PerlMonks site front end has:

Results (25 votes). Check out past polls.

Notices?
 • erzuuli ‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.