Schwartzian transform explained

Did you google for "explain schwartzian transform"?

If yes, then you've come to the right place. If no, then you've come to the right place (I wouldn't want to loose out on a prospective reader now, would I?). Please read on - you will find this worth your time.

This post aims to dissect the Schwartzian Transform, and explains it through an example. And while doing this, it shows how cool Perl is.

But what is the Schwartzian Transform? - A way to efficiently sort a list of items.

Why the name? - Legend has it that Randal "Merlyn" Schwartz (wiki page) demonstrated a Perlish version of a Lisp idiom to speed up sorting. And since that day, every time you use the word "Schwartzian Transform", somewhere far beyond the distant seas, the Randal smiles.

How does it speed up sorting? - Patience my child. The blooming of a flower is an analog process, revealing each petal gracefully unlike the open-throw-catch-roll-close process of a frog's tongue. (Yummy?)

Why do I need to know it? - Because it's fun.

Will each line be preceded by a question in the bold font? - Not from now on.

Suppose you have an array of salesman objects - @salesmen, each of which consists of the following attributes:

1. name           # salesman name
2. base_salary    # base salary
3. n_cust_conned  # number of customers conned
4. comm_per_sale  # commission per sale

And the sub routine which calculates the total salary of the salesman is:

sub get_total_sal {
    my ($obj) = @_;
    my $total_salary = $obj->{base_salary} + 
                       $obj->{n_cust_conned} * $obj->{comm_per_sale};
    return $total_salary;
}

If you were told to sort this array based on the total salary, what would be your code snippet which does the sort?

Without prior knowledge of the transform, maybe something like this:

my @sorted_salesmen = sort { $a->get_total_sal() 
                             <=>
                             $b->get_total_sal() } @salesmen;

This would do the job. But what limitation does it induce in your code?

Think about it.

 The reader thinks, muses and ponders. Birds migrate. Tectonic plates shift. Radioactive elements decay.

The shortcoming is the get_total_sal() call is made for each comparision. Why?

Suppose you wanted to hand sort the following sample data based on the total salary code as shown above:

my @salesmen_info = (
    {
      name          => 'sp1',    
      base_salary   => 1000,
      n_cust_conned => 2,
      comm_per_sale => 100
    },
    {
      name          => 'sp2',    
      base_salary   => 500,
      n_cust_conned => 4,
      comm_per_sale => 200
    },
    {
      name          => 'sp3',    
      base_salary   => 700,
      n_cust_conned => 3,
      comm_per_sale => 100
    },
);

1. Compare sp1 and sp2 - as sp1 < sp2 keep them as it is. (sp1, sp2, sp3)

2. Compare sp1 and sp3 - as sp3 < sp1 swap sp3 and sp1. (sp3, sp2, sp1)

3. Compare sp2 and sp1 - as sp1 < sp2 swap sp2 and sp1. (sp3, sp1, sp2)

Without consciously thinking, what was the first thing that you did with the data? - Calculate the total sal and then start the comparison, so that you don't need to calculate total salary again and again. Remember that.

Now let us revisit our sorting snippet,

my @sorted_salesmen = sort { $a->get_total_sal() 
                             <=>
                             $b->get_total_sal() } @salesmen;

Perl internally uses merge sort as of Perl 5.7 but for the sake of understanding let us assume that for the sample data, the above snippet sorts as we hand sorted it.

Step 2: Compare sp1 and sp3 => this leads to get_total_sal() being called for sp1 and sp3.

But didn't we call get_total_sal for sp1 during Step 1? Why do we need to call get_total_sal() again for sp1?

A moment's silence.

Bulbs flash, eyebrows are raised, jaws drop and you smile with your newly acquired wisdom.

What if we had a way to store the total salary of each salesman so that the sort {} block does not cause the extra overhead of calling the get_total_sal() sub multiple times for the objects whose total salary was already calculated during an earlier comparison?

That's exactly what the Schwartzian transform does.

With the Schwartzian Saber you'd rewrite your sorting snippet like so:

  my @sorted_salesmen = map  { $_->[0]}
                        sort { $a->[1] <=> $b->[1] }
                        map  { [$_, $_->get_total_sal()] }
                        @salesmen;

If you can read this, this means your brain did not explode. Congratulations.

If the above code snippet makes perfect sense - get up, wear a stupid grin on your face, and stay smug all day long. If it doesn't make any sense - read on - your hubris is just a few sentences away.

Let's read the snippet in a bottom up fashion. Pre-requisite - you know what map does. Read the man page here

1. Get each element of the salesmen array.

@salesmen;

2. Map each element and create an array of array references, each of which contains the object as the first element and the total salary as the second element. This is the place where you record each salesman's salary one and only one time.

  map  { [$_, $_->get_total_sal()] }
  @salesmen;

3. Sort this array of array references where the comparator is the 2nd element of each array element - i.e. the total salary that you calculated in step 2.

  sort { $a->[1] <=> $b->[1] }
  map  { [$_, $_->get_total_sal()] }
  @salesmen;

4. What does Step 3 return? - A sorted array of array references where first element is the salesman object and the 2nd element is the total salary. But what do we need? - just an array of salesman objects - the 2nd element of each array ref containing the total salary is of no use to us now. So we extract what we need via map:

  my @sorted_salesmen = map  { $_->[0]}
                        sort { $a->[1] <=> $b->[1] }
                        map  { [$_, $_->get_total_sal()] }
                        @salesmen;

How many times did we call the get_total_sal() sub? Once per each object as compared to the previous method where in we called it once per each comparison.

Of course, the speedup that you gain is dependent on how heavy/light your get_total_sal() is + the size of your input data. Use it wisely.

Schwartz on!!