Schwartzian Transform Website Links For
Transform 		 

Information About

Schwartzian Transform
  CATEGORIES ABOUT SCHWARTZIAN TRANSFORM
   
programming idioms
   
sorting algorithms
   
articles with example perl code
   
perl
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



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. It is a special case of Memoization , which would work for any algorithm.


ALGORITHM DESCRIPTION


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)


Unless the modification times are memoized for each file, this method requires their re-computing every time a file is compared in the sort. The Schwartzian transform solution is to change the code 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[2
}

transformedArray := sort(transformedArray, simpleCompare)

for each file in transformedArray
insert transformedArray {Link without Title} 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 { -> {Link without Title} } # extract original list elements
sort { -> <=> ->[1 } # sort list by keys
map { -M } # pair up list elements with keys
@files_array;


IMPLEMENTATION IN PYTHON


Python programmers also use the transform in sorts 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)


The key function can return a tuple of values if secondary and further sort keys are desired. If the default sort for the keys is not enough, a comparator function can be given with an additional keyword argument cmp, for example:


# python2.4
new_list = sorted(old_list, key=f, cmp=lambda a,b:cmp(a or cmp(b[1 ,a[1]))


Note that the key function f should do the expensive work as it's called only once for each key whereas the comparator function is called each time the sort algorithm has to compare two elements. The function sorted is new in Python 2.4, before that only method sort was available and more than one statement was required. The key function is also new in Python 2.4 so in Python 2.3 one had to spell out the transform in a way similar to the following:


# python2.3
new_list = x) for x in old_list
new_list.sort()
new_list = for x in new_list


If desired, a comparator function can be given to the sort here as well.


IMPLEMENTATION IN RUBY


Ruby programmers have their own shortcut.


# ruby