Perl: Sort Misc

Sorting in Perl

here's a example of sort (Perl 5.8):

#-*- coding: utf-8 -*-
# perl

@li = (1,9,2,3);

@li2 = sort {$a <=> $b} @li; # original list is not changed

print join(' ', @li2); # 1 2 3 9

In Perl, sort is a function. 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 operand is less than the right operand. 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 do a Perl equivalent of a Python example above.

#-*- coding: utf-8 -*-
#  perl

@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

Side Note: Perl also has pure function construct. In Perl, a pure function is simply written as sub {…}, and applied to argument by the form pureFunction->(arg). For example, a function that squares a number and applied to 3 is written as: sub {$_^2} -> (3).

Unlike Python, Perl has no limitation in its pure function construct. Because of this, Perl supports better functional programing than Python (albeit still limited). Here's a simple example:

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

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

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

# 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 inordinately unusual among imperative languages, in both its semantics and syntax, it has acquired a coolness factor among monkey 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.

perldoc -f sort