Addendum to the tutorial on Sorting in Perl and Python at:
http://xahlee.org/perl-python/sort_list.html


Language and Sort Optimization: decorate-sort-dedecorate

2006-08-27

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.

Xah
xah@...
∑ http://xahlee.org/


☄