Schwartzian transform

The Schwartzian transform is a technique in computer programming used to efficiently sort an array by using the result of a computation-heavy operation without re-computing that result for every comparison performed by the sort subroutine. While the practice is named after Randal L. Schwartz, who popularized it among Perl programmers, its use in computer science dates back at least as far as the Common Lisp standard.

Related Topics:
Computer programming - Sort - Array - Subroutine - Randal L. Schwartz - Perl - Common Lisp

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 a < b

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

transformedArray := sort(transformedArray, simpleCompare)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for each file in transformedArray

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

insert transformedArray 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 { $_-> }

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

sort { $a-> $b-> }

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

map { }

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

@files_array;

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Python programmers also use the Schwartzian transform when it is desired to sort a list where the comparison operation may be expensive.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In this example, f(x) returns a key which is suitable for using for sorting. For instance, it might return the length of x, or it might do a database lookup based on the value of x.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• python2.4

new_list = sorted(old_list, key=f)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• python2.3

new_list =

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

new_list.sort()

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

new_list = for x in new_list]

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Ruby's sort_by method (as of version 1.8) is implemented using a Schwartzian transform.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

new_list = old_list.sort_by {|file| file.mtime }

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

 
Schwartzian transform: External links ►