From: Daniel Carrera <dcarrera@...>
Date: 2003-01-12T12:03:30+09:00
Subject: sorting with the Swartzian transform

Hello all,

This email is simply for the benefit and/or reading pleasure of ruby
hackers.  In particular those without a strong Perl background.  I just
had to do a Swartzian transform in Ruby and it occurred to me that someone
might benefit from my experience.

If you already know how to do a Swartzian transform in Ruby, just skip.


The Swartzian transform is a method of speeding up certain expensive
sorts.  It is one of the hallmarks of Perl, and it is also available in
Ruby (I actually like it better in Ruby).

Situation:
==========
Say I have an array of objects and want to sort them according to some
criteria.  Suppose I have a function that assigns a numerical value for
each object.  The simplest way to do the sort is:

array.sort { |a,b| myFunction(a) <=> my_function(b)}

Here, my_function() gets called O(n log n) times.  If my_function() is
expensive, this sort can be very slow.  This is where the Swartzian
transform comes in.

step 1:
=======
Use Array#map to create a new array whose entries are arrays containing
both the original object and the corresponding my_function() value.

array.map { |obj|  [ my_function(obj), obj] }

This is an O(n) operation.

step 2:
=======
Sort this array

   . sort { |a,b| a[0] <=> b[0] }

This is O(n log n), but the operations are cheap.

step 3:
=======
Now use Array#map again to get rid of the myFunction() values.

    . map { |arr| arr[1] }


The whole thing looks like this:

sorted = array.map  { |obj| [ my_function(obj), obj ] }\
              .sort { |a,b|   a[0] <=> b[0] }\
              .map  { |arr|   arr[1] }


This is actually much more readable than the Perl version (which has to be
written backwards).

A general case:
===============
Suppose you can't assign numerical values to the objects.  All you have is
a compare() function.  Normally you'd write:

sorted = array.sort { |a,b| compare(a,b) }

There might still be room for a Swartzian transform.  You can try to do as
much work as possible on a sepparate function, and create a fast_compare()
function that does the rest of the work.  The the transform would look
like:

sorted = array.map  { |obj| [ prepare_object(obj), obj ] }\
              .sort { |a,b|   fast_compare(a,b) }\
              .map  { |arr|   arr[1] }

The more work you can pull out of 'fast_compare()' and put into
'prepare_object()' the faster the sort will be.

I hope someone benefits from this.

Cheers,
Daniel Carrera
Graduate Teaching Assistant.  Math Dept.
University of Maryland.  (301) 405-5137