Shwartzian Transform

I was trying to merge sort a list of files based on their last modified date when someone said to me “do a schwartzian”. Now, I had no idea what they were talking about so off to google I went.

It’s basically this (shamelessly ripped from the excellent Wikipedia article):

@sorted = map  { $_->[0] }
                  sort   { $a->[1] cmp $b->[1] }
                  map  { [$_, foo($_)] }
                           @unsorted;

Reading from right to left (or from the bottom to the top):

• the original list @unsorted is fed into a map operation that wraps each item into a (reference to an anonymous 2-element) array consisting of itself and the calculated value that will determine its sort order (list of item becomes a list of [item=>value]);
• then the list of lists produced by map is fed into sort, which sorts it according to the values previously calculated (list of [item, value] => sorted list of [item, value]);
• finally, another map operation unwraps the values (from the anonymous array) used for the sorting, producing the items of the original list in the sorted order (sorted list of [item, value] => sorted list of item).

The use of anonymous arrays ensures that memory will be reclaimed by the Perl garbage collector immediately after the sorting is done.

The computational savings obtained by the Schwartzian transform depend strongly on the structure of the inner function. For an efficient ordinary sort function, the number of invocations of the transform function goes from an average of 2nlogn to n; one should carefully consider on a case-by-case basis whether the extra implementation complexity is justified by this efficiency saving.

It’s worth noting that foo() is a method that returns the value that an element will be sorted against and that $a and $b are special Perl variables that you can read more about in the sort documentation.

Pretty neat!

Related posts:

1. Mad-Lib Perl Snippet

Tagged as: perl