Pradeep K. Pant Blog


Perl’s hidden treasure (The Schwartzian Transform)


If you ask me about the best features of Perl then there will be many answers CPAN, Hashes, RegX etc etc but the one of the hidden feature of perl is The Schwartzian Transform. This is a technique that allows you to efficiently sort by a computed, secondary index.  Let’s say that you wanted to sort a list of strings by their md5 sum.  Pl. see the code below (the comments below are best read from bottom).

my @strings = (‘C’, ‘CPlusPlus’, ‘Java’, ‘Perl’);

my $sorted_strings_on_MD5 =

map { $_->[0] } # map back to the original value

sort { $a->[1] cmp $b->[1] } # sort by the correct element of the list

map { [$_, MD5Calu_func($_)] } #  create a list of anonymous lists

@strings #  take strings

Where MD5Calu_func($) represents an expression that takes $ (each item of the list in turn) and produces the corresponding value that is to be compared. This way,  you only have to do the expensive md5 computation N times, rather than N log N times. That’s the beauty of algorithm.

The algorithm has been given by one of the greatest guy is Perl community Randal L. Schwartz.

Happy reading!



Copyright © 2007-2024 PRADEEP K. PANT

Source Code | RSS