Last year, i've posted a tutorial and commentary about Python and

Perl's sort function. (http://xahlee.org/perl-python/sort_list.html)

In that article, i discussed a technique known among juvenile Perlers

as the Schwartzian Transform, which also manifests in Python as its

“key” optional parameter.

Here, i give a more detailed account on why and how of this construct.

----

Language and Sort Optimization: decorate-sort-dedecorate

There are many algorithms for sorting. Each language can chose which to

use. See wikipedia for a detailed list and explanation:

Sorting_algorithm↗ .

However, does not matter which algorithm is used, ultimately it will

need the order-deciding function on the items to be sorted. Suppose

your items are (a,b,c,d,...), and your order-deciding function is F.

Various algorithms will try to minimize the number of times F is

called, but nevertheless, F will be applied to a particular element in

the list multiple times. For example, F(a,b) may be called to see which

of “a” or “b” comes first. Then, later the algorithm might need

to call F(m,a), or F(a,z). The point here is that, F will be called

many times on arbitrary two items in your list, even if one of the

element has been compared to others before.

Now suppose, you are sorting some polygons in 3D space, or personal

records by the person's address's distance from a location, or sorting

matrixes by their eigen-values in some math application, or ordering

files by number of occurrences of some text in the file.

In general, when you define your decision function F(x,y), you will

need to extract some property from the elements to be sorted. For

example, when sorting points in space by a criterion of distance, one

will need to compute the distance for the point. When sorting personal

records from database by the person's location, the decision function

will need to retrieve the person's address from the database, then find

the coordinate of that address, that compute the distance from there to

a given coordinate. In sorting matrixes in math by eigen-values, the

order-decision will first compute the eigen-value of the matrix. A

common theme from all of the above is that they all need to do some

non-trivial computation on each element.

As we can see, the order-decision function F may need to do some

expensive computation on each element first, and this is almost always

the case when sorting elements other than simple numbers. Also, we know

that a sorting algorithm will need to call F(x,y) many times, even if

one of x or y has been compared to others before. So, this may result

high inefficiency. For example, you need to order people by their

location to your home. So when F(Mary,Jane) is called, Mary's address

is first retrieved from a database across a network, the coordinate of

her address is looked up in another database. Then the distance to your

home are computed using spherical geometry. The exact same thing is

done for Jane. But later on, it may call F(Mary,Chrissy),

F(Mary,Jonesy), F(Mary,Pansy) and so on, and the entire record

retrieval for Mary is repeated many times.

One solution, is to do the expensive extraction one time for each

element, then associate that with the corresponding elements. Suppose

this expensive extraction function is called gist(). So, you create a

new list ([Mary,gist(Mary)], [Jane,gist(Jane)], [John,gist(John)],

[Jenny,gist(Jenny)], ...) and sort this list instead, when done, remove

associated gist. This technique is sometimes called

decorate-sort-dedecorate.

In Perl programing, this decorate-sort-dedecorate technique is sillily

known as Schwartzian Transform as we have demonstrated previously. In

Python, they tried to incorporate this technique into the language, by

adding the “key” optional parameter, which is our gist() function.

----------

This post is archived at:

http://xahlee.org/perl-python/sort_list.html

I would be interested in comments about how Common Lisp, Scheme, and

Haskell deal with the decorate-sort-dedecorate technique. In

particular, does it manifest in the language itself? If not, how does

one usually do it in the code? (note: please reply to approprate groups

if it is of no general interest. Thanks) (am also interested on how

Perl6 or Python3000 does this, if there are major changes to their sort

function)

Thanks.

Xah

xa*@xahlee.org

∑ http://xahlee.org/