Sunday, November 28, 2010

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()] }

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.


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()] }

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()] }

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()] }

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!!


Jignesh Gangani said...

And Developers are supposed to write maintainable and easily understandable code. Sure, the features the programming languages allows you to write one-line-for-matrix-transpose code (or i = i + 1), but over the time even the person who wrote the code would not be able to explain it to other. Good Luck maintainers. (That can be yourself).

Saurabh said...

@Mr.J: I am surprised that you thought that Schwartzian transform hampers readability. It thwarts readability as much as the usage of bit vectors to check/set/reset flags in C - if one does not know how it works - the code will look complicated. Its usage has become almost instinctive now when I work with Perl.

Complexity is contextual. When you break it down into simple steps, its not that hard. Not using the advanced features of a language just because of the thought that a future maintainer won't be able to understand it is like directing a braindead formula movie just because your audience won't be able to appreciate creativity.

chorny said...

Jignesh: There are 2 different types of readability: for beginners and for professionals. In this case if you expect beginner to read your code, it is enough to put comment #Schwartzian transform.

LeoNerd said...

See also sort_by in List::UtilsBy. It uses a variation of the Schwartzian internally, using a neater syntax:

my @sorted_salesmen = sort_by { $_->get_total_sal() } @salesmen;

Saurabh said...

@Leo:Thanks. That's a neat module you've got there. Checked out your blog. You have a good collection of posts. Will go through them.

Ether Rain said...

I ended up reading this because I thought i was stupid and couldn't figure it out. It turned out that the book I was reading didn't format the friggen code right, because as soon as I got to the example, it was prettty obvious what it did, and I am a beginner perl programmer, and it does not seem too hard at all. In fact, one of the easier Idioms I've seen (compared to some of the ones in C++ that can get pretty complicated, especially when dealing with templates).