Perl中著名的Schwartzian转换问题解决实现
程序员文章站
2022-04-09 10:22:54
...
Perl中著名的Schwartzian转换,其产生背景主要涉及到排序问题:
比如说,根据文件名以字母顺序排序,代码如下:
比如说,根据文件名以字母顺序排序,代码如下:
复制代码 代码如下:
use strict;
use warnings;
my @files = glob "*.xml"; #perl中文件操作符glob提供相当于shell中的通配符的功能
my @sorted_files = sort @files; #sort(),排序,默认是字母顺序排序
比如说,根据文件名长度排序,其代码如下:
use strict;
use warnings;
my @files = glob "*.xml"; #perl中文件操作符glob提供相当于shell中的通配符的功能
my @sorted_files = sort @files; #sort(),排序,默认是字母顺序排序
比如说,根据文件名长度排序,其代码如下:
复制代码 代码如下:
use strict;
use warnings;
#length求长度。 太空船操作符,默认变量是$a,$b,返回值为-1,0,1分别表示大于,==,小于。 sort进行排序
my $files = ".xml";
my @sorted_length = sort { length($a) length($b) } @files;
上面的两种情况,对很多文件操作来说,速度还不算慢,如果是下面这种情况。
比如说:要批量比较文件大小,其代码如下:
use strict;
use warnings;
#length求长度。 太空船操作符,默认变量是$a,$b,返回值为-1,0,1分别表示大于,==,小于。 sort进行排序
my $files = ".xml";
my @sorted_length = sort { length($a) length($b) } @files;
上面的两种情况,对很多文件操作来说,速度还不算慢,如果是下面这种情况。
比如说:要批量比较文件大小,其代码如下:
复制代码 代码如下:
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中的默认的变量,并存储到内存中!于是又下面算法实现:
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中的默认的变量,并存储到内存中!于是又下面算法实现:
复制代码 代码如下:
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],比较它们的值。得到另一个二维数组。
第三步:丢掉文件大小元素,创建一个只含文件名的列表。完成目标!
上面的代码使用了两个临时数组,但这并不是必须的。我们可以一个语句就能完成所有的工作。为了达到目的,需要按照“数据从右流向左”的原理反转句子顺序,不如果将每个句子放在单独一行,并且留出足够的空间,我们依然可以写出可读性高的代码。
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],比较它们的值。得到另一个二维数组。
第三步:丢掉文件大小元素,创建一个只含文件名的列表。完成目标!
上面的代码使用了两个临时数组,但这并不是必须的。我们可以一个语句就能完成所有的工作。为了达到目的,需要按照“数据从右流向左”的原理反转句子顺序,不如果将每个句子放在单独一行,并且留出足够的空间,我们依然可以写出可读性高的代码。
复制代码 代码如下:
my @quickly_sorted_files =
map { $_->[0] }
sort { $a->[1] $b->[1] }
map { [$_, -s $_] }
@files;
这就是以Randal L. Schwartz命名的Schwartzian转换,对数据量特多的情况下,其速度要比前者快数倍!
下面写了小程序,包括在生成1万个xml文件,在两种情况下,完整代码如下:
my @quickly_sorted_files =
map { $_->[0] }
sort { $a->[1] $b->[1] }
map { [$_, -s $_] }
@files;
这就是以Randal L. Schwartz命名的Schwartzian转换,对数据量特多的情况下,其速度要比前者快数倍!
下面写了小程序,包括在生成1万个xml文件,在两种情况下,完整代码如下:
复制代码 代码如下:
#!/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;
}
#!/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
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
相关文章
相关视频
专题推荐
-
独孤九贱-php全栈开发教程
全栈 170W+
主讲:Peter-Zhu 轻松幽默、简短易学,非常适合PHP学习入门
-
玉女心经-web前端开发教程
入门 80W+
主讲:灭绝师太 由浅入深、明快简洁,非常适合前端学习入门
-
天龙八部-实战开发教程
实战 120W+
主讲:西门大官人 思路清晰、严谨规范,适合有一定web编程基础学习
上一篇: PHP比较全的友好时间显示
下一篇: PHPEXCEL的用法与简介
网友评论
文明上网理性发言,请遵守 新闻评论服务协议
我要评论