Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Many people are familiar with the advanced sorting technique called the Schwartzian Transform also referred to as the ST which is of course named after our very own merlyn.

The basic idea of this technique is to speed up sorts where complex functions are required to be called to put the data into order by precomputing the various keys that will be used. The precomputed keys, and the actual item is usually wrapped in an anonymous array (or anonymous hash, basically any kind of transitory container) through a map, the output of which is then sorted based on the contents of the various keys, and then fed into another map that unwraps the payload and returns the original values, but in the correct order. This process can result in signifigant time savings. An example of the technique is as follows. Lets say we have a list of words, and we want to sort them by the number of 'e's present in each word, then by the actual word. Using the ST we would do something like this:

my @words=qw(The time has come the Walrus said to speak of many things +); my @sorted=map { pop @$_ } sort{ $a->[0] <=> $b->[0] || $a->[1] cmp $b->[1] } map { [tr/eE/eE/,$_] } @words;
The Guttman Rosler Transform or GRT is a variant (refinement) of this technique that attempts to avoid using a perl inorder function for the sort (as it is perl code is slower than the internal lexicographical or numeric sorting which is implemented in C) and to avoid the overhead of creating many (potentially thousands) of anonymous arrays (or containers, they need not be arrays after all).

The basic idea is to encode the precomputed keys into a string, usually using pack() such that perl can sort them lexicographically (also called ascii sort or char sort). Thus the above sort can be transformed into

my @sorted=map { substr($_,4) } sort map { pack("LA*",tr/eE/eE/,$_) } @words;

Generally speaking the GRT is a signifigant improvement on the ST, although it can be a bit tricky to work out the appropriate pack/unpack functions. (Unless you're tye of course ;-)

Anyway, enough of my explanations, anybody who wishes to learn more about this technique and other advanced sorting techniques should get it from the horses mouth and have a look at the excellent article A Fresh Look at Efficient Perl Sorting

Recent Update: tye has come up with two excellent nodes that cover both the ST and GRT and some practical variants. Check em out: Re^2: Stable sorting in Perl (old) and fast, flexible, stable sort
Updates: fixed typos, added clarification :-)

Yves / DeMerphq
--
When to use Prototypes?


In reply to Advanced Sorting - GRT - Guttman Rosler Transform by demerphq

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others about the Monastery: (4)
    As of 2014-08-30 12:48 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (293 votes), past polls