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

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

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?

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.