|Perl: the Markov chain saw|
Advanced Sorting - GRT - Guttman Rosler Transformby demerphq (Chancellor)
|on Feb 15, 2002 at 10:47 UTC||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:
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
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
Yves / DeMerphq