排序变换思路：施瓦茨变换

637 0 0

作者:骏马金龙

施瓦茨变换(Schwartzian Transform)是一种排序思路。先看看它的结构：

my @output_data =
    map { EXTRACTION },
    sort { COMPARISON }
    map [ CONSTRUCTION ],
@input_data;

施瓦茨变换：

construction：构造一个由原始数据以及被处理后准备用来做排序属性的元素组成的列表A
comparison：从列表A中取得元素进行排序，得到排序后列表B
expraction：从列表B中取得原始元素得到新列表C
列表C就是期待的排序结果

先举个例子，文件test.txt中的内容如下：

1     mac     2000    500
2     winxp   4000    300
3     bsd     1000    600
4     linux   1000    200
5     SUSE    4000    300
6     Debian  600     200

现在需要使用perl对该文件进行排序，以第三字段为主排序依据(升序)，第四字段(升序)、第一字段(降序)分别为辅助排序依据。

下面这种代码是谁都会的：

open DATA,"<","/perlapp/test.txt"
    or die "Can't open file: $!";

print sort {
                my @x = split / +/,$a;
                my @y = split / +/,$b;
                $x[2] <=> $y[2] 
                or $x[3] <=> $y[3]
                or $y[0] <=> $x[0]
           } <DATA>;

上面的排序过程中，对每一行都进行了一次split函数处理，换句话说，每一次比较操作都进行了两次split。

使用施瓦茨变换，可以将每次比较过程中每一种函数的多次操作都减少为一次，正如上面的split可以减少为一次(性能并没有更优化，只是代码减少了，更漂亮了)。

以下是使用Schwartzian Transform实现上述排序需求的代码：

open DATA,"<","/perlapp/test.txt" or die "Can't open file: $!";

print map { $_->[0] }
      sort { 
          $a->[3] <=> $b->[3] 
          or $a->[2] <=> $b->[2] 
          or $b->[1] <=> $a->[1] }
      map { [ $_,split / +/,$_ ] } <DATA>;

在上面施瓦茨变换代码中(从下往上看)：

最后一个map函数，将<DATA>中的元素重新构建成了一个新的匿名列表A，这个列表中除了原始文件中的每一行数据，还有对每一行进行split后的元素，因为每一行都是空格分隔的，所以split后的每一个元素都直接作为匿名列表的元素。大概如下：["6 Debian 600 200","6","Debian","600","200"]
sort函数对匿名列表A进行排序，取列表A中需要排序的元素进行排序，排序后得到一个新的排序列表B，这个列表中仍然包含了原始数据和split后的各元素，只不过它们是经过排序后的
第一个map函数从排序后的列表B中取出第一个元素，也就是文件中的元素数据，得到最终的排序列表C

很多地方说施瓦茨变换会提高排序性能，但实际上并没有，原来sort的排序方式对每个$a $b都进行了split，其实就是对每一行都进行split，施瓦茨变换后对每一行都进行split，实际上它们是一样的，只不过施瓦茨变换后是对整个<DATA>预先split好，而不是每次取$a $b的时候进行split。

也就是说，施瓦茨变换仅仅只是让sort排序的时候，取数据更直接而已，并没有提升性能。

内容来源于网络如有侵权请私信删除

标签： Python Python开发 Python语言

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

排序变换思路：施瓦茨变换