Perl Language Sorting The Schwartzian Transform
Example
This is probably the most famous example of a sort optimization making use of Perl's functional programming facilities, to be used where the sort order of items depend on an expensive function.
# What you would usually do
@sorted = sort { slow($a) <=> slow($b) } @list;
# What you do to make it faster
@sorted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ $_, slow($_) ] }
@list;
The trouble with the first example is that the comparator is called very often and keeps recalculating values using a slow function over and over. A typical example would be sorting file names by their file size:
use File::stat;
@sorted = sort { stat($a)->size <=> stat($b)->size } glob "*";
This works, but at best it incurs the overhead of two system calls per comparison, at worst it has to go to the disk, twice, for every single comparison, and that disk may be in an overloaded file server on the other side of the planet.
Enter Randall Schwartz's trick.
The Schwartzian Transform basically shoves @list through three functions, bottom-to-top. The first map turns each entry into a two-element list of the original item and the result of the slow function as a sort key, so at the end of this we have called slow() exactly once for each element. The following sort can then simply access the sort key by looking in the list. As we don't care about the sort keys but only need the original elements in sorted order, the final map throws away the two-element lists from the already-sorted list it receives from @sort and returns a list of only their first members.
