设为首页 加入收藏

TOP

排序变换思路:施瓦茨变换
2018-10-10 04:10:34 】 浏览:115
Tags:排序 变换 思路 瓦茨

施瓦茨变换(Schwartzian Transform)是一种排序思路。先看看它的结构:
my @output_data =
    map { EXTRACTION },
    sort { COMPARISON }
    map [ CONSTRUCTION ],
@input_data;


施瓦茨变换:


现在需要使用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>;


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


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


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


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇简化 Django 开发的八个 Python 包 下一篇Perl正则表达式超详细教程

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目