Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^5: RFC:A brief tutorial on Perl's native sorting facilities.

by Jenda (Abbot)
on Feb 06, 2007 at 22:02 UTC ( [id://598649]=note: print w/replies, xml ) Need Help??


in reply to Re^4: RFC:A brief tutorial on Perl's native sorting facilities.
in thread RFC:A brief tutorial on Perl's native sorting facilities.

Yes, you would ask the object to give you a key (or generate the key based on some of the objects' properties) and use that to populate the @keys array in my example or the keys in the two item arrays of ST. The thing is that the GT prepends the key (either using . or pack()) to the stringified values of the items, sorts the results and then strips the keys. It's not a matter of outperforming, it's a matter of either returning useless stuff or having to bend backwards and ending up with copies.

Let's assume you have an array containing hashes like this and want to sort them by, let's say, the birth_date:

@list = ( {fname => 'Jan', lname => 'Krynicky', birth_date => 'Sep 3 1975', #... }, {fname => 'Pavel', lname => 'Krynicky', birth_date => 'Dec 25 1969', #... }, {fname => 'Martin', lname => 'Krynicky', birth_date => 'Aug 24 1973', #... }, );
Sort this using GRT!

use Date::Calc qw(Decode_Date_US); use Data::Dumper; sub convertdate { return sprintf '%04d%02d%02d', Decode_Date_US($string) } # ST @sorted = map{ $_->[1] } sort{ $a->[0] <=> $b->[0] } map{ [ convertdate($_->{birth_date}), $_ ] } @list; print Dumper(\@sorted); # @keys array { my @keys = map convertdate($_->{birth_date}), @list; @sorted = @list[ sort {$keys[$a] cmp $keys[$b]} (0..$#list) ]; } print Dumper(\@sorted); # GRT @sorted = map{ ## Chop off the bit we added. substr( $_, 8 ) } sort map{ ## Note: No comparison block callback. ## Extract the field as before, but concatenate it with the origin +al element ## instead of building an anonymous array containing both elements +. convertdate($_->{birth_date}) . $_ } @list; print Dumper(\@sorted);
Whoops?!?
$VAR1 = [ 'HASH(0x18db494)', 'HASH(0x224e9c)', 'HASH(0x224fa4)' ];
?!?

Replies are listed 'Best First'.
Re^6: RFC:A brief tutorial on Perl's native sorting facilities.
by jdporter (Paladin) on Feb 06, 2007 at 22:27 UTC

    Did you really expect that to work?

    The easiest way to do what you're trying to do is to sort the array indices, rather than the array elements directly.

    my @sorted = @list[ map { substr( $_, 8 ) } sort map { convertdate( $list[$_]->{birth_date} ) . sprintf "%06d", $_ } 0 .. $#list ];

    This is essentially identical to tye's fast, flexible, stable sort.

    A word spoken in Mind will reach its own level, in the objective world, by its own weight

      No of course I did not expect it to work. I was showing BrowserUK that it doesn't. I feel stupid for not noticing that I could merge the "sort indices" trick and GRT though to get the best from both worlds. The speed of GRT and the generality of the other styles of complex sort. Silly me. Thanks!

        I was just about to respond in the same way as jdporter, but I thought I'd run a benchmark first. To my surprise, the key sort is faster than the indexed GRT! Assuming my benchmark isn't screwed:

        #! perl -slw use strict; use Date::Calc qw(Decode_Date_US); use Data::Dumper; use Benchmark qw[ cmpthese ]; sub convertdate { return sprintf '%04d%02d%02d', Decode_Date_US( $_[0] ) } our @list = ( { fname => 'Jan', lname => 'Krynicky', birth_date => 'Sep 3 1975', } +, { fname => 'Pavel', lname => 'Krynicky', birth_date => 'Dec 25 1969' +, }, { fname => 'Martin', lname => 'Krynicky', birth_date => 'Aug 24 1973 +', }, map{ { fname => $_, lname => 'Krynicky', birth_date => 'Jan 1 ' . ( 1900 + int( rand 100 ) ) } } 1 .. $ARGV[ 0 ] || 100 ); cmpthese -1, { ST => q[ my @sorted = map{ $_->[1] } sort{ $a->[0] <=> $b->[0] } map{ [ convertdate($_->{birth_date}), $_ ] } @list; ], KEY => q[ { my @keys = map convertdate($_->{birth_date}), @list; @sorted = @list[ sort {$keys[$a] cmp $keys[$b]} (0..$#list +) ]; } ], GRTish => q[ my @sorted = @list[ map { substr( $_, 8 ) } sort map { convertdate( $list[$_]->{birth_date} ) . $_ } 0 .. $#list ]; ], };

        the keyed sort works out between 20 and 35% faster for this application.

        s/iter ST GRTish KEY ST 1.67 -- -4% -24% GRTish 1.61 4% -- -21% KEY 1.27 32% 27% -- C:\test>junk9 1 Rate GRTish ST KEY GRTish 21914/s -- -10% -19% ST 24349/s 11% -- -10% KEY 27113/s 24% 11% -- C:\test>junk9 1e2 Rate GRTish ST KEY GRTish 986/s -- -1% -16% ST 997/s 1% -- -15% KEY 1179/s 20% 18% -- C:\test>junk9 1e3 Rate ST GRTish KEY ST 71.2/s -- -11% -25% GRTish 80.3/s 13% -- -16% KEY 95.1/s 34% 19% -- C:\test>junk9 1e4 Rate ST GRTish KEY ST 6.31/s -- -9% -23% GRTish 6.90/s 9% -- -16% KEY 8.23/s 30% 19% --

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://598649]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others studying the Monastery: (5)
As of 2024-04-24 00:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found