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 [EMAIL PROTECTED] ∑ http://xahlee.org/ -- http://mail.python.org/mailman/listinfo/python-list