当前位置：首页 > 资讯 > 技术文档

Perl中著名的Schwartzian转换问题解决实现

时间：2021-06-03 02:35 编辑：来源：阅读：
扫一扫，手机访问

摘要：Perl中著名的Schwartzian转换问题解决实现

Perl中著名的Schwartzian转换，其产生背景主要涉及到排序问题: 比如说，根据文件名以字母顺序排序，代码如下:

use strict; 

use warnings; 

my @files = glob "*.xml";          #perl中文件操作符glob提供相当于shell中的通配符的功能 

my @sorted_files = sort @files;    #sort()，排序，默认是字母顺序排序

比如说，根据文件名长度排序，其代码如下:

[u]复制代码[/u] 代码如下:

use strict; 

use warnings; 

#length求长度。 太空船操作符<=>，默认变量是$a,$b，返回值为-1,0,1分别表示大于，==，小于。 sort进行排序 

my $files = ".xml"; 

my @sorted_length = sort { length($a) <=> length($b) } @files;

上面的两种情况，对很多文件操作来说，速度还不算慢，如果是下面这种情况。比如说:要批量比较文件大小，其代码如下:

[u]复制代码[/u] 代码如下:

use strict; 

use warnings; 

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中的默认的变量，并存储到内存中！于是又下面算法实现:

[u]复制代码[/u] 代码如下:

use strict; 

use warnings; 

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]，比较它们的值。得到另一个二维数组。第三步:丢掉文件大小元素，创建一个只含文件名的列表。完成目标! 上面的代码使用了两个临时数组，但这并不是必须的。我们可以一个语句就能完成所有的工作。为了达到目的，需要按照“数据从右流向左”的原理反转句子顺序，不如果将每个句子放在单独一行，并且留出足够的空间，我们依然可以写出可读性高的代码。

[u]复制代码[/u] 代码如下:

my @quickly_sorted_files = 

    map  { $_->[0] } 

    sort { $a->[1] <=> $b->[1] } 

    map  { [$_, -s $_] } 

    @files;

这就是以Randal L. Schwartz命名的Schwartzian转换，对数据量特多的情况下，其速度要比前者快数倍！下面写了小程序，包括在生成1万个xml文件，在两种情况下，完整代码如下:

[u]复制代码[/u] 代码如下:

#!/usr/bin/perl -w 

use strict; 

use warnings; 

use autodie; 

use v5.10; 

###################################### 

###  创建要比较的10,000个.xml文件 ### 

###################################### 

my $profix = ".xml"; 

foreach my $num (1..10000) { 

    open(my $fh, '>', $num . $profix) || die "Can not create the file: $!\n"; 

    print $fh "This is file size testing!"; 

} 

print "All the 10_1000 files created! \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;

输出结果: All the 10_1000 files created! 常规算法需要时间: => 185 Schwartzian算法需要时间: => 115

全部评论(0)

上一篇：在Debian下配置Python+Django+Nginx+uWSGI+MySQL的教程
下一篇：为Python程序添加图形化界面的教程

资讯排行榜
更多>>