Perl-Python-a-Day: Sorting

[Xah Lee]

Sorting in Perl

In Perl, to sort a list, do like this:

@li=(1,9,2,3);
@li2 = sort {$a <=> $b} @li;
print join(' ', @li2);


In Perl, sort is a function, not some Object Oriented thing. It returns
the sorted result as another list. This is very simple and nice.

It works like this: sort takes the form “sort {...} @myList”.
Inside the enclosing braces is the body of the ordering function, where
variables $a and $b inside are predefined by the language to represent
two elements in the list. The operator “<=>” returns -1 if left
element is less than right element. If equal, it returns 0, else 1. It
is equivalent to Python's “cmp” function.

Perl provides another comparison operator “cmp”, which treats its
operands as strings. So, for example:

print "3" <=> "20"; # prints -1
print "3" cmp "20"; # prints 1


In Perl, numbers and strings are mutually automatically converted if
needed.

Another form of sort is “sort orderFunctionName @list”, which uses
a function name in place of the comparison block

Just for completeness, let's define a Perl equivalent of a Python
example above.

@li=(
'my283.jpg',
'my23i.jpg',
'web7-s.jpg',
'fris88large.jpg',
);

# sorts a list of strings by their embedded number
@li2 = sort { ($a=~m/(\d+)/)[0] <=> ($b=~m/(\d+)/)[0];} @li;
print join(' ', @li2);  # prints web7-s.jpg my23i.jpg fris88large.jpg
my283.jpg


Note, that Perl also has pure functions (lambda) construct. In Perl, a
pure function is simply done as “def {...}”, and applied to
argument by the form “pureFunction->(args)”. Unlike Python, Perl
has no limitation in its pure function construct. Because of this, Perl
supports a limited form of functional programing. Here's a simple
example:

$result = sub($) {$_[0]+1}->(3);
print $result; # prints 4
# a value obtained by a pure function that adds 1 to its argument,
# applied to a argument of 3.


Perl, like Python, whose compiler is not very smart. In sorting, the
ordering function is called unnecessarily repetitiously. Like Python,
Perlers have sought means to avoid this penalty. If the programer knew
in advance that his matrix is huge or knew in advance his ordering
function, then he can code his sort by writing it using a very complex
workaround.:

Here's how this work around works: Suppose you want to sort a huge list
with a expensive ordering function. If you simply do “sort
orderingFunction @myList”, then Perl is going to call your
orderingFunction wantonly, and you lose. To beat Perl, you first
generate a copy newList, whose elements are pairs (x,y), where x is
from the original list, and y is the sorting key extracted from x.
Then, you call Perl's sort function on this newList and using a
ordering function based on the second list element (the y). Once this
newList is sorted, you construct your original list by extracting the
first element from this sorted newList. Here's the code example:

# the following two lines are equivalent
@li2 = sort { ($a=~m/(\d+)/)[0] <=> ($b=~m/(\d+)/)[0];} @li;
@li2 = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_,
($_=~m/(\d+)/)[0] ] } @li;


In the above Perl code, the part “map { [ $_, ($_=~m/(\d+)/)[0] ] }
@li;” generates the intermediate newList. Then, sort is applied to
it, then, another map “map { $_->[0] }” gets the original list
sorted.

In this way, the cost of the internals of the ordering function is
avoided. (it runs on each list element once) However, your huge list is
copied 1 extra time. So, there are pros and cons. Because this work
around is very complex in both its semantics and syntax, it has
acquired a coolness factor among Perl coders, and is given the name
Schwartzian Transform.

It is interesting to note what compiler flaws can do to imperative
languages and its people. In Python, the language syntax is tainted. In
Perl, a complex construct is invented. In both camps, the basic
mathematics of sorting and its implementation aspects are completely
belied.

For the official doc of Perl's sort, type on the command line:
“perldoc -f sort”.
---------
this post is archived at:
http://xahlee.org/perl-python/sort_list.html

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