i see your schwartz is bigger than mine
A week or two ago a perl 6 enthusiast friend of mine mentioned how he’d, “just used a Schwartzian transform to answer a guys question in #perl” during the brief passing of an otherwise routine instant message conversation.
Knowing nothing about the Schwartzian transform — in fact, only hearing of its existence for the first time — and not wanting to look like a narc in front of my nerd fanboy friend. I did what any self-respecting good guy would do. I turned to the google.
I skimmed through the wikipedia page felt slightly confused, read it properly and gained a better understanding. I also happened on this page which lists the implementation of the Schwartzian tranform in several different languages. Except one, your favourite AND mine: JavaScript.
So I decided I would implement a Schwartzian transform in JavaScript and design a crude test to see the performance benefits for myself.
The test sorts arrays of strings — containing numbers with thousands separators — in ascending order of lengths: 20, 200, 800, 1600 & 2000; and uses arrays in descending order, as well as randomly ordered arrays.
Before I explain the benefits of using a Schwartzian transform over a regular sort, I’ll go through the code required to implement a Schwartzian transform.
As it turns out, this is hella-easy and — the actual sort — only requires one line of code, if you like squeezing code onto one line. For the purposes of explaining this technique though, I will be more verbose.
function getValue( o ) {
/* returns a specific value from item: o */
}
function compareFunction( a, b ) { // depending on how you want to sort, asc or desc, your sort function would look something like this
var _a = a[1], _b = b[1];
return _a == _b ? 0 : _a < _b ? -1 : 1;
}
var unsorted_array = [/* array of stuff */], // the schwartz starts here
paired_array = unsorted_array.map( function( o ) { return [o, getValue( o )]; } ),
paired_array_sorted = paired_array.sort( compareFunction ),
sorted_array = paired_array_sorted.map( function( o ) { return o[0]; } );
Breaking it down
unsorted_array — is the array of unsorted values we want to sort.
paired_array — is the result of iterating through unsorted_array to create and return, a new array, of tuples, containing the original item and the value we want to sort on. This would look something like this:
[[original_item_1, sort_value_1], [original_item_2, sort_value_2], ..., [original_item_N, sort_value_N]]
paired_array_sorted — is the result of sorting paired_array, though as sorting happens inline, paired_array_sorted is the same as paired_array.
sorted_array — is the result of iterating through paired_array_sorted and returning the first, original, item from each tuple.
Putting it all on one line we can get something like this:
sorted_array = unsorted_array.map( function( o ) { return [o, getValue( o )]; } ).sort( compareFunction ).map( function( o ) { return o[0]; } );
What’s the benefit of using a Schwartzian tranform?
When I first saw this, I thought it was kind of complex and that running a map on the array we want to sort, twice, was excessive. But have a look at the code for just using a regular sort:
function getValue( o ) {
/* returns a specific value from item: o */
}
function compareFunction( a, b ) { // depending on how you want to sort, asc or desc, your sort function would look something like this
var _a = getValue( a ), _b = getValue( b );
return _a == _b ? 0 : _a < _b ? -1 : 1;
}
var unsorted_array = [/* array of stuff */],
sorted_array = unsorted_array.sort( compareFunction );
At first glance this looks much more elegant, I mean there is a lot less code. But in actual fact this sort can take a significantly longer amount of time to complete than the Schwartzian tranform sort, depending on the time it takes to retrieve each value from the getValue function. Why?
…the Schwartzian transform actually reduced the order of complexity of the number of times the keys are calculated from O(N*log(N)) to O(N).
Optimizing Code for Speed - wikibooks
In plain english this means:
- Using the Schwartzian method, we calculate the values we want to sort on, for every item in the array, ONCE, storing them with their original item in a new array.
- Using a regular sort, we are calculating the values we want to sort on, EVERY TIME the sort function compares two items in the array.
Chart time!
So with this post almost at an end, it’s time to display a chart, showing the efficiency of the Schwartzian tranform over a regular sort, for the test I created.
I ran the test in the latest stable versions of each browser on a MacBook Pro with OS X 10.6.3. Except Internet Explorer which I tested using a VM running Windows XP. Sorry the graph times aren’t incrementing nicely, Internet Explorer’s times blow the whole graph out and I wanted to show the distributions more clearly.
As you can see though, in each browser the Schwartzian transform far out performs a regular sort for this test.
Conclusion
The Schwartzian transform is a simple method we can use to improve the performance of sorting arrays of items, where the values we wish to sort on involve expensive calculations. However, you should always consider when to use this method on a case by case basis.
PS. This is NOT an April fools’ day prank. :¬P
