Perl中著名的Schwartzian转换问题解决实现
Perl中著名的Schwartzian转换，其产生背景主要涉及到排序问题:
比如说，根据文件名以字母顺序排序，代码如下:
usestrict; usewarnings; my@files=glob"*.xml"; #perl中文件操作符glob提供相当于shell中的通配符的功能 my@sorted_files=sort@files; #sort()，排序，默认是字母顺序排序
比如说，根据文件名长度排序，其代码如下:
usestrict;
usewarnings;
#length求长度。太空船操作符<=>，默认变量是$a,$b，返回值为-1,0,1分别表示大于，==，小于。sort进行排序
my$files=".xml";
my@sorted_length=sort{length($a)<=>length($b)}@files;
上面的两种情况，对很多文件操作来说，速度还不算慢，如果是下面这种情况。
比如说:要批量比较文件大小，其代码如下:
usestrict;
usewarnings;
my@files =glob"*.xml";
my@sort_size=sort{-s$a<=>-s$b}@files; #比较大小
上面的代码设计到三重(次)操作:
1.从硬盘上获取文件大小(-s$b)
2.比较文件大小(太空船操作)
3.对其进行排序(sort操作)
考虑到要比较$a,$b大小时，要从硬盘中获取两次，所以次数是6次！也就是说，如果有1万个文件，总共是6万次。
其算法复杂度是:n*long(n),考虑到后两项(比较文件大小，进行排序)必然要进行的操作，但第一项却可以降低！
即一次性从硬盘中读取所有文件大小，将其放置到Perl中的默认的变量，并存储到内存中！于是又下面算法实现:
usestrict;
usewarnings;
my@files=glob"*.xml";
my@unsorted_pairs=map {[$_,-s$_]}@files;
my@sorted_pairs =sort{$a->[1]<=>$b->[1]}@unsorted_pairs;
my@sorted_files =map {$_->[0]}@sorted_pairs;
看上去比较复杂，分三个步骤解释下:
第一步:遍历文件列表，对每个文件创建一个数组引用。数组引用包含两个元素：
第一个是文件名($_)，第二个是文件大小(-s$_)。这样，处理每个文件只访问一次磁盘。
第二步:对二维数组排序。因比较文件大小，所以需取元素[1]，比较它们的值。得到另一个二维数组。
第三步:丢掉文件大小元素，创建一个只含文件名的列表。完成目标!
上面的代码使用了两个临时数组，但这并不是必须的。我们可以一个语句就能完成所有的工作。为了达到目的，需要按照“数据从右流向左”的原理反转句子顺序，不如果将每个句子放在单独一行，并且留出足够的空间，我们依然可以写出可读性高的代码。
my@quickly_sorted_files=
map {$_->[0]}
sort{$a->[1]<=>$b->[1]}
map {[$_,-s$_]}
@files;
这就是以RandalL.Schwartz命名的Schwartzian转换，对数据量特多的情况下，其速度要比前者快数倍！
下面写了小程序，包括在生成1万个xml文件，在两种情况下，完整代码如下:
#!/usr/bin/perl-w
usestrict;
usewarnings;
useautodie;
usev5.10;
######################################
### 创建要比较的10,000个.xml文件###
######################################
my$profix=".xml";
foreachmy$num(1..10000){
open(my$fh,'>',$num.$profix)||die"Cannotcreatethefile:$!\n";
print$fh"Thisisfilesizetesting!";
}
print"Allthe10_1000filescreated!\n";
######################################
###常规转换: 遍历20次 ###
######################################
my$t1 =time();
foreach(1..20){
my@files =glob"*.xml";
my@sorted =sort{-s$a<=>-s$b}@files;
}
say"常规算法需要时间:=>",time()-$t1;
######################################
###Schwartzian转换:遍历20次 ###
######################################
my$t2 =time();
foreach(1..20){
my@files=glob"*.xml";
my@sorted=
map {$_->[0]}
sort{$a->[1]<=>$b->[1]}
map {[$_,-s$_]}
@files;
}
say"Schwartzian算法需要时间:=>",time()-$t2;