[zt] 高效排序之施瓦茨转换

兰花仙子

有人在Perl邮件列表上提了个问题，要求对如下数组的内容按指定规则进行排序：

my @array = qw(c r v vr tr re c.p[1] c.p[3] c.p[2] c.p[4] c.p[7]
c.p[6] c.p[5] c.p[8] c.t[1] c.t[3] c.t[2]);
I only want to sort the elements that have a numeric value inside the braces so that all the other elements have their original index preserved.

简言之，对@array数组的内容，按c.p[N], c.t[N]这里的N值进行升序排序，其他元素位置不变，要求输出形式如下：
c r v vr tr re c.p[1] c.p[2] c.p[3] c.p[4] c.p[5] c.p[6] c.p[7] c.p[8] c.t[1] c.t[2] c.t[3]

原提问者自己提到了施瓦茨转换，一种排序算法。但其他回答者认为这个不好用施瓦茨转换来做。
正好我对这种排序方法很熟悉，花了2分钟时间就写出来了：

        1.        my @new = map { $_->[0] }
        2.            sort { $a->[1]->[0] cmp $b->[1]->[0] or
        3.            $a->[1]->[1] <=> $b->[1]->[1] }
        4.            map {[$_,[ $_=~/\.(.+)\[(\d+)\]/ ]]}
        5.            @array;

现在@new数组就包含了排序后的内容，输出的结果是提问者所需要。
这种排序法在Perl里要倒着看，从第5行看到第1行（如果用ruby实现，就正着看，因为ruby的数组是个对象，map, sort是对象方法，从左往右调用）。

第5行是原始数组，第4行的map方法针对原始数组再产生一个临时数组，第2-3行的sort方法针对这个临时数组，按指定规则进行排序，
排序的结果又是一个临时数组，第1行的map从最后产生的临时数组里，提取出所需要的值，就是我们想要的结果。

施瓦茨转换是Perl黑客Randal L. Schwartz发明的，维基上有详细介绍：
http://en.wikipedia.org/wiki/Schwartzian_transform

sjdy521

乍一看，只觉得为了应付数据的特点而map出了一个新的数据结构方便排序而已，倒是没看到所谓的高效之处。
我再去wiki上仔细读一下吧

sjdy521

哈哈 wiki里的Efficiency analysis分析的很清楚了，多谢仙子分享，虽然平时可能写过类似的形式，但都没意识到这已经是一个很著名的 Perl programming idiom 啦

yybmsrs

c r v vr tr re这些也顺带排序了，如果最后再加个c，估计就不是想要的了

kk861123

yybmsrs 发表于 2012-08-30 17:17
c r v vr tr re这些也顺带排序了，如果最后再加个c，估计就不是想要的了

正如楼上所担心，我给扩展了一下

1. my @array = qw(c r v vr tr re c.p[1] c.p[3] c.p[2] d c.p[4] c.p[7] c.p[6] c.p[5] c.p[8] c.t[1] c.t[3] c.t[2]);
   
2. 
   
3. my @maps =  map { [ $_ , [ $_ =~ /[.](\w)\[(\d)\]/ ] ] }@array;
   
4. my @sort = sort { $a->[1]->[0] cmp $b->[1]->[0]
   
5.                   or
   
6.                   $a->[1]->[1] <=> $b->[1]->[1]}
   
7.            grep { @{$_->[1]} } @maps;
   
8. 
   
9. my $i = 0;
   
10. my @new  =  map { @{$_->[1]} ? $sort[$i++]->[0] : $_->[0] }@maps;
    
11. 
    
12. print "@new\n";

复制代码

sjdy521

回复 5# kk861123


    代码帝，实践帝，每次看你帖子总是代码。。

kk861123

回复 6# sjdy521

{:3_185:}
   

cdtits

想到、做到

pitonas

仔细读一下这高效{:2_172:}