目前有很多排序算法(
快速排序
，
冒泡排序
，
归并排序
, etc.)
根据输入的不同，有的快些，有的慢些。 Perl曾经使用快速排序，
之后换成了归并排序。 今天，如果你需要的话，可以通过
sort
指令选择排序方式。
无论你选择那一种，平均来看，至少需要N*log(N)比较。 这就意味着，对于N = 1000个文件，perl需要访问2 * 1000 * 3 = 6000次磁盘。
(两倍于比较次数。) 对每个文件，perl要获取6次大小! 这明显是很大的浪费。
我们不能避免访问磁盘来获取文件大小，我们也不能减少比较次数，但是，我们可以减少访问磁盘的次数。
预先获取文件大小
我们会预先获取所有文件大小，把它们存在内存，然后对内存中的数据排序。
my @unsorted_pairs = map { [$_, -s $_] } @files;
my @sorted_pairs = sort { $a->[1] <=> $b->[1] } @unsorted_pairs;
my @quickly_sorted_files = map { $_->[0] } @sorted_pairs;
这可能比之前写的复杂一些，不过先忍一下，还有个更简单的方式。
总共分为3个步骤。首先遍历文件列表，对每个文件创建一个数组引用。数组引用包含两个元素：第一个是文件名，第二个是文件大小。这样，处理每个文件只访问一次磁盘。
第二步，对二维数组（每个文件是一个一维数组）排序。在比较小数组时，我们取元素[1]，比较它们的值。得到的结果是另一个二维数组。
第三步，丢掉文件大小元素，创建一个只含文件名的列表。完成目标结果。
Schwartzian 转换
上面的代码使用了两个临时数组，但这并不是必须的。我们可以一个语句就能完成所有的工作。为了达到目的，需要按照“数据从右流向左”的原理反转句子顺序，不如果将每个句子放在单独一行，并且留出足够的空间，我们依然可以写出可读性高的代码。
my @quickly_sorted_files =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, -s $_] }
@files;
这就是以
Randal L. Schwartz
命名的
Schwartzian 转换
。
在代码里，通过map-sort-map的结构可以很容易就认出这种转换方法。
这种方法可以用来对任何东西排序，尤其是比较计算频繁的情况。
my @sorted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, f($_)] }
@unsorted;
使用这种算法对3000个xml文件排序“仅仅”比ASCII排序慢10倍，比刚开始的代码快8倍。
实际上，在获得速度提升的同时，我们需要付出内存和代码复杂度增高的代价。对于小数组来说不值得，对大数组只有在真正对程序产生实际影响时才划算。
如果整个排序需要1秒钟，而脚本需要跑10分钟，就没有必要。相反，如果排序在整个运行时占用很大比重，你就应该使用Schwartzian转换方法。
为了找出你处于那种情况，可以在代码中使用
Devel::NYTProf to profile
。
(Thanks to
Smylers
for reviewing the article.)
If you have any comments or questions, feel free to post them on the source of this page in GitHub.
Source on GitHub.
Comment on this post
