|
|
Schwartzian TransformThe Schwartzian transform is a technique in computer programming devised by Randal Schwartz and used heavily in Perl, although the concept can be applied to most programming languages. The technique is used to efficiently sort an array by using the result of a computation-heavy operation without re-computing that result for every instance of the sort subroutine. For example, to sort a list of files by their modification times, a novice approach might be as follows: function naiveCompare(file a, file b) { return modificationTime(a) < modificationTime(b) } // Assume that sort(list, comparisonPredicate) sorts the given list using // the comparisonPredicate to compare two elements. sortedArray := sort(filesArray, naiveCompare) However, this method requires re-computing the modification times of each file every time that file is compared in the sort. This code can be rewritten using the Schwartzian transform as follows: for each file in filesArray insert array(file, modificationTime(file)) at end of transformedArray function simpleCompare(array a, array b) { return a2 < b2 } transformedArray := sort(transformedArray, simpleCompare) for each file in transformedArray insert transformedArray1 at end of sortedArray This code performs several steps to achieve a quicker result: First, the top loop iterates through each element of filesArray, creating an anonymous array reference for each element. The anonymous array has two elements: the current element of filesArray and the modification time of that file. Second, the list of anonymous array references returned by the first map is sorted. The list is sorted according to the second elements of each anonymous array. Finally, the sorted list of array references is iterated over by the bottom loop. This loop simply builds the sorted array from the first element of each array reference, which is the name of the file. Perl's compact list-manipulation functions can perform the entire transform in a single statement, although it must be written "backwards": @sorted_array = map { $_->0 } sort { $a->1 <=> $b->1 } map { -M $_ } @files_array;
|
 |