Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

Faster than the speed of sound (was: When the Best Solution Isn't)

by Aristotle (Chancellor)
on Sep 23, 2002 at 17:02 UTC ( #200165=note: print w/replies, xml ) Need Help??

in reply to Re: Re^2: When the Best Solution Isn't
in thread When the Best Solution Isn't

You know (leaving the in-place assignment issue aside), it occured to me (duh) that this is a general purpose but faster rephrasing of the Schwartzian Transform:
sub sxsorta (&;) { my $sort_key = shift; my @rank = map &$sort_key, @_; @_[ sort { $rank[$a] cmp $rank[$b] } 0 .. $#_ ]; } sub sxsortn (&;) { my $sort_key = shift; my @rank = map &$sort_key, @_; @_[ sort { $rank[$a] <=> $rank[$b] } 0 .. $#_ ]; }

The gains over the regular ST comes from the fact that it doesn't create hundreds of tiny anonymous arrays, and that the sort callback is slightly faster because it only has to do an array lookup but no dereferencing.

The drawback is that with a lexically scoped (as it should be) @rank, there's no way to pass a userspecified callback to the routines without inflicting a massive performance hit. To do more complex sorts, one therefor has to separately spell this idiom out in their own code.

Makeshifts last the longest.

  • Comment on Faster than the speed of sound (was: When the Best Solution Isn't)
  • Download Code

Replies are listed 'Best First'.
Re: Faster than the speed of sound (was: When the Best Solution Isn't)
by blakem (Monsignor) on Sep 23, 2002 at 17:58 UTC
    That looks a lot like a method used in Effective Perl Programming (see item 14 in the idiomatic perl pdf)

    The goal is to sort /etc/passwd by the third field:

    open PASSWD, "/etc/passwd" or die; @passwd = <PASSWD>; @key = map # Create an array @key contain +ing { (split /:/)[2] } @passwd; # just the keys (user ids). @by_uid_index = sort { # Sort indices, using @key arr +ay. $key[$a] <=> $key[$b] } 0 .. $#key; @by_uid = @passwd[@by_uid_index]; # Now, rearrange the contents +of # @passwd into sorted order. Or just combine the last two statements: @by_uid = @passwd[sort { $key[$a] <=> $key[$b] } 0 .. $#key];
    Well, this will work, and it's efficient enough, but there are prettier, more Perl-ish ways to present the solution.
    It then goes on to describe the Orcish and Schwartzian under the heading of 'Advanced sorting: the cool ways'


      Interesting. It's more verbose with the extra array, and the Schwartzian Transform is such a common idiom one should definitely know it, but I wonder if the author(s) had any particular motive to recommend the ST over this meme?

      Makeshifts last the longest.

        Perhaps because the ST is named after the books co-author? ;-)

        Actually, that unnamed sorting method sits right between "sorting: the mundane way" and "sorting: the cool way". Guess they just liked the Orcish and ST better.


Re: Faster than the speed of sound (was: When the Best Solution Isn't)
by demerphq (Chancellor) on Apr 16, 2003 at 23:10 UTC

    Just for the record this technique is sometimes called a Guttman Rosler Transform.


    <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

      Sorry, that’s incorrect.

      1. The point of the GRT is to call upon sort without a callback attached.

        (This is done by packing all the sortkeys and the actual data into a single datum in such a way that a simple $a cmp $b, which is the default sort behaviour, will result in the desired order (hence its alternative name “packed-default sort”).)

      2. The GRT (and the ST alike) directly sorts the elements themselves, with an extra step to extract the payload from each element afterwards.

      The approach I’m using here differs on both counts. It uses a sort callback, unlike the GRT, and sorts indices, unlike both the ST and the GRT.

      Its similarity is in having an extra step before sorting and another after, where the before-sorting step has the same purpose in all cases, i.e. computing the sort key for each element only once. The storage used for the computed keys differs greatly for each approach though, and therefore so do their after-sorting steps.

      Makeshifts last the longest.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (7)
As of 2019-12-12 15:44 GMT
Find Nodes?
    Voting Booth?

    No recent polls found