简简单单讲sort--perl

概述仙子地址：http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=636546 简简单单讲sort 仙子注：本文档和仙子前面的2篇文档"简简单单讲grep"，"简简单单讲map"，都译自网络，加上仙子自己的解释整理而成。原文档出自： http://web.archive.org/web/20041123005900/http://www.rayc

仙子地址：http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=636546

简简单单讲sort

仙子注：本文档和仙子前面的2篇文档"简简单单讲grep"，"简简单单讲map"，都译自网络，加上仙子自己的解释整理而成。原文档出自：

http://web.archive.org/web/20041123005900/http://www.raycosoft.com/rayco/support/perl_tutor.HTML
文档的Author是位Perl Hacker，曾在Microsoft和T-Mobile工作。要理解他的全部Code并不容易，也许偶讲的也不是很清楚，所以，读者自己也要多动脑筋哦。
（一） sort函数
sort List
sort BLOCK List
sort SUBname List
sort的用法有如上3种形式。它对List进行排序，并返回排序后的列表。假如忽略了SUBname或BLOCK，sort按标准字串比较顺序来进行（例如ASCII顺序）。如果指定了SUBname，它实际上是个子函数的名字，该子函数对比2个列表元素，并返回一个小于，等于，或大于0的整数，这依赖于元素以何种顺序来sort（升序，恒等，或降序）。也可提供一个BLOCK作为匿名子函数来代替SUBname，效果是一样的。
被比较的2个元素，会被临时赋值给变量$a和$b。它们以引用传递，所以不要修改$a或$b。假如使用子函数，它不能是递归函数。
（二） 用法示例
1. 以数字顺序sort
@array = (8,2,32,1,4,16);
print join(' ',sort { $a <=> $b } @array),"\n";
打印结果是：
1 2 4 8 16 32
与之一样的是：
sub numerically { $a <=> $b };
这个很容易理解哦，它只是按自然数的顺序进行sort，偶就不细讲了。
2.1 以ASCII顺序（非字典顺序）进行sort
@languages = qw(fortran lisp c c++ Perl python java);
打印结果：
Perl c c++ fortran java lisp python
这等同于：
按ASCII的顺序进行排序，也没什么说的哦。
注意，如果对数字按ASCII顺序进行sort的话，结果可能与你想的不同：
1 10 11 2 3 4 5 6 7 8 9
2.2 以字典顺序sort
use locale; 
@array = qw(ASCII ascap at_large atlarge A ARP arp);
@sorted = sort { ($da = lc $a) =~ s/[\W_]+//g;
                 ($db = lc $b) =~ s/[\W_]+//g;
                 $da cmp $db;
               } @array;
print "@sorted\n";
A ARP arp ascap ASCII atlarge at_large
use locale是可选的--它让code兼容性更好，假如原始数据包含国际字符的话。use locale影响了cmp,lt,le,ge,gt和其他一些函数的 *** 作属性--更多细节见perllocale的man page。
注意atlarge和at_large的顺序在输出时颠倒了，尽管它们的sort顺序是一样的（sort中间的子函数删掉了at_large中间的下划线）。这点会发生，是因为该示例运行在perl 5.005_02上。在perl版本5.6前，sort函数不会保护有一样values的keys的先后顺序。perl版本5.6和更高的版本，会保护这个顺序。
注意哦，不管是map,grep还是sort，都要保护这个临时变量$_（sort里是$a和$b）的值，不要去修改它。在该code里，在对$a或$b进行替换 *** 作s/[\W_]+//g前，先将它们重新赋值给$da和$db，这样替换 *** 作就不会修改原始元素哦。
3. 以降序sort
降序sort比较简单，把cmp或<=>;前后的 *** 作数调换下位置就可以了。
sort { $b <=> $a } @array;
或者改变中间的块或子函数的返回值的标记：
sort { ($a <=> $b) } @array;
或使用reverse函数（这有点低效，但也许易读点）：
reverse sort { $a <=> $b } @array;
4. 使用多个keys进行sort
要以多个keys来sort，将所有以or连接起来的比较 *** 作，放在一个子函数里即可。将主要的比较 *** 作放在前面，次要的放在后面。
# An array of references to anonymous hashes
@employees = ( 
    { FirsT =>; 'Bill',   LAST =>; 'Gates',     
      SALARY =>; 600000,AGE =>; 45 },
    { FirsT =>; 'George',LAST =>; 'Tester'     
      SALARY =>;  55000,AGE =>; 29 },250)">    { FirsT =>; 'Steve',  LAST =>; 'Ballmer',   
    { FirsT =>; 'Sally',  LAST =>; 'Developer', 
    { FirsT =>; 'Joe',    LAST =>; 'Tester',    
);
sub seniority {
    $b->;{SALARY}     <=>;  $a->;{SALARY}
    or $b->;{AGE}     <=>;  $a->;{AGE}
    or $a->;{LAST}    cmp  $b->;{LAST}
    or $a->;{FirsT}   cmp  $b->;{FirsT}
}
@ranked = sort seniority @employees;
foreach $emp (@ranked) {
    print "$emp->;{SALARY}\t$emp->;{AGE}\t$emp->;{FirsT} 
        $emp->;{LAST}\n";
600000  45      Bill Gates
600000  41      Steve Ballmer
55000   29      Sally Developer
55000   29      George Tester
55000   29      Joe Tester
上述code看起来很复杂，实际上很容易理解哦。@employees数组的元素是匿名hash。匿名hash实际上是个引用，可使用->; *** 作符来访问其值，例如$employees[0]->;{SALARY}可访问到第一个匿名hash里SALARY对应的值。所以上述各项比较就很清楚了，先比较SALARY的值，再比较AGE的值，再比较LAST的值，最后比较FirsT的值。注意前2项比较是降序的，后2项是升序的，不要搞混了哦。
5. sort出新数组
@x = qw(matt elroy jane sally);
@rank[sort { $x[$a] cmp $x[$b] } 0 .. $#x] = 0 .. $#x;
print "@rank\n";
2 0 1 3
这里是否有点糊涂呀？仔细看就清楚了。0 .. $#x是个列表，它的值是@x数组的下标，这里就是0 1 2 3。$x[$a] cmp $x[$b] 就是将@x里的各个元素，按ASCII顺序进行比较。所以sort的结果返回对@x的下标进行排序的列表，排序的标准就是该下标对应的@x元素的ASCII顺序。
还不明白sort返回什么？让我们先打印出@x里元素的ASCII顺序：
print join ' ',sort { $a cmp $b } @x;
打印结果是：elroy jane matt sally
它们在@x里对应的下标是1 2 0 3，所以上述sort返回的结果就是1 2 0 3这个列表了。@rank[1 2 0 3] = 0 .. $#x 只是个简单的数组赋值 *** 作，所以@rank的结果就是(2 0 1 3)了。
6. 按keys对hash进行sort
%hash = (Donald =>; knuth,Alan =>; Turing,John =>; Neumann);
@sorted = map { { ($_ =>; $hash{$_}) } } sort keys %hash;
foreach $hashref (@sorted) {
    ($key,$value) = each %$hashref;
    print "$key =>; $value\n";
Alan =>; Turing
Donald =>; knuth
John =>; Neumann
上述code不难明白哦。sort keys %hash按%hash的keys的ASCII顺序返回一个列表，然后用map进行计算，注意map这里用了双重{{}}，里面的{}是个匿名hash哦，也就是说map的结果是个匿名hash列表，明白了呀？
所以@sorted数组里的元素就是各个匿名hash，通过%$hashref进行反引用，就可以访问到它们的key/value值了。
7. 按values对hash进行sort
%hash = ( Elliot =>; Babbage,250)">          Charles =>; Babbage,250)">          Grace =>; Hopper,250)">          Herman =>; Hollerith
        );
@sorted = map { { ($_ =>; $hash{$_}) } } 
              sort { $hash{$a} cmp $hash{$b}
                     or $a cmp $b
                   } keys %hash;
Charles =>; Babbage
Elliot =>; Babbage
Herman =>; Hollerith
Grace =>; Hopper
本文作者如是说，偶觉得很重要：
与hash keys不同，我们不能保证hash values的唯一性。假如你仅根据values来sort hash，那么当你增或删其他values时，有着相同value的2个元素的sort顺序可能会改变。为了求得稳定的结果，应该对value进行主sort，对key进行从sort。
这里{ $hash{$a} cmp $hash{$b} or $a cmp $b } 就先按value再按key进行了2次sort哦，sort返回的结果是排序后的keys列表，然后这个列表再交给map进行计算，返回一个匿名hash列表。访问方法与前面的相同，偶就不详叙了。
8. 对文件里的单词进行sort，并去除重复的
perl -0777ane '$,= "\n"; \
   @uniq{@F} = (); print sort keys %uniq' file
大家试试这种用法，偶也不是很明白的说，:(
@uniq{@F} = ()使用了hash slice来创建一个hash，它的keys是文件里的唯一单词；该用法在语意上等同于$uniq{ $F[0],$F[1],... $F[$#F] } = ()。
各选项说明如下：
-0777    -   读入整个文件，而不是单行
-a       -   自动分割模式，将行分割到@F数组
-e       -   从命令行读取和运行脚本
-n       -   逐行遍历文件：while (<>;) { ... }
$,       -   print函数的输出域分割符
file     -   文件名
9. 高效sorting: Orcish算法和Schwartzian转换
对每个key，sort的子函数通常被调用多次。假如非常在意sort的运行时间，可使用Orcish算法或Schwartzian转换，以便每个key仅被计算1次。
考虑如下示例，它根据文件修改日期来sort文件列表。
# 强迫算法--对每个文件要多次访问磁盘
@sorted = sort { -M $a <=>; -M $b } @filenames;
# Orcish算法--在hash里创建keys
@sorted = sort { ($modtimes{$a} ||= -M $a) <=>;
                 ($modtimes{$b} ||= -M $b)
               } @filenames;
很巧妙的算法，是不是？因为文件的修改日期在脚本运行期间是基本不变的，所以-M运算一次后，把它存起来就可以了呀。偶就经常这么用的，:p
如下是Schwartzian转换的用法：
@sorted = map( { $_->;[0] }   
               sort( { $a->;[1] <=>; $b->;[1] }
                     map({ [$_,-M] } @filenames)
                   )
             );
这个code结合用了map,sort分了好几层，记住偶以前提过的方法，从后往前看。map({ [$_,-M] } @filenames)返回一个列表，列表元素是匿名数组，匿名数组的第一个值是文件名，第二个值是文件的修改日期。
sort( { $a->;[1] <=>; $b->;[1] }...再对上述产生的匿名数组列表进行sort，它根据文件的修改日期进行sort。sort返回的结果是经过排序后的匿名数组。
最外围的map( { $_->;[0] }...就简单了，它从上述sort产生的匿名数组里提取出文件名。这个文件名就是根据修改日期进行sort过的呀，并且每个文件只运行了一次-M。
这就是著名的Schwartzian转换，这种用法在国外perl用户里很流行。记住仙子告诉你的Schwartzian概念哦，下次就不会被老外laugh at了，:p
本文作者说：
Orcish算法通常更难于编码，并且不如Schwartzian转换文雅。我推荐你使用Schwartzian转换作为可选择的方法。
也请记住基本的优化code的规则：(1)不写code；(2)在使code快速之前，先保证其正确；(3)在使code快速之前，先让它清楚。
10. 根据最后一列来对行进行sort（Schwartzian转换）
假如$str的值如下（每行以\n终结）：
eir    11   9   2   6   3   1   1   81%   63%   13
oos    10   6   4   3   3   0   4   60%   70%   25
hrh    10   6   4   5   1   2   2   60%   70%   15
spp    10   6   4   3   3   1   3   60%   60%   14
按最后1个域的大小进行sort:
$str = join "\n",250)">            map { $_->;[0] }
                sort { $a->;[1] <=>; $b->;[1] }
                     map { [ $_,(split)[-1] ] }
                         split /\n/,$str; 
让我们从后往前，一步一步看上述code：
split /\n/,$str; 这里返回一个列表，列表元素就是各个行了。
map { [ $_,(split)[-1] ] } 这里的map求得一个匿名数组列表，匿名数组的值分别是整行，和该行的最后一列。使用Schwartzian转换时，这步是关键哦，记着用map来构造你自己的匿名数组列表，匿名数组的第1个元素是最终需要的值，第2个元素是用于比较的值。
sort { $a->;[1] <=>; $b->;[1] } 对上1步中产生的匿名数组，按第2个元素进行sort，它返回sort后的匿名数组列表。
map { $_->;[0] } 对上1步中sort后的匿名数组，提取出第1个元素，也就是整行哦。

也许你会说：“怎么这么麻烦呀？偶不想用这种方式。”那么，可用CPAN上的现成模块来代替：
use Sort::FIElds;
@sorted = fIEldsort [ 6,'2n','-3n' ] @lines;
CPAN的模块文档很详细的，自己看看呀。
11. 重访高效sorting: Guttman-Rosler转换
考虑如下示例：
@dates = qw(2001/1/1  2001/07/04  1999/12/25);
你想按日期升序对它们进行排序，哪种方法最有效呢？
最直观的Schwartzian转换可以这样写：
@sorted = map { $_->;[0] }
          sort { $a->;[1] <=>; $b->;[1]
                 or $a->;[2] <=>; $b->;[2]
                 or $a->;[3] <=>; $b->;[3]
               }
          map { [ $_,split m</>; $_,3 ] } @dates;
然而，更高效的Guttman-Rosler转换(GRT)这样写：
@sorted = map { substr $_,10 }
          sort
          map { m|(\d\d\d\d)/(\d+)/(\d+)|;
                sprintf "%d-%02d-%02d%s",$1,$2,$3,$_
              } @dates;
GRT方法难于编码，并且比Schwartzian转换更难阅读，所以我推荐仅在极端环境下使用GRT。使用大的数据源，perl 5.005_03和linux 2.2.14进行测试，GRT比Schwartzian转换快1.7倍。用perl 5.005_02和windows NT 4.0 SP6进行测试，GRT比Schwartzian快2.5倍。
另外，perl 5.6及更高版本的sort使用Mergesort算法，而5.6之前的sort使用Quicksort算法，前者显然快于后者，所以，要想求速度，也要升级你的perl版本哦。
（三）CPAN上关于sort的一些模块
file::Sort - Sort one or more text files by lines
Sort::FIElds - Sort lines using one or more columns as the sort key(s)
Sort::ArbBiLex - Construct sort functions for arbitrary sort orders
Text::BibTeX::BibSort - Generate sort keys for bibliographic entrIEs.
自己在CPAN上search和read哦，偶不详解了，:P 总结

以上是内存溢出为你收集整理的简简单单讲sort--perl全部内容，希望文章能够帮你解决简简单单讲sort--perl所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。