快捷導(dǎo)航

Perl中著名的Schwartzian轉(zhuǎn)換問(wèn)題解決實(shí)現(xiàn)

更新時(shí)間：2015年06月02日 17:54:02 投稿：junjie

這篇文章主要介紹了Perl中著名的Schwartzian轉(zhuǎn)換問(wèn)題解決實(shí)現(xiàn),本文詳解講解了Schwartzian轉(zhuǎn)換涉及的排序問(wèn)題,并同時(shí)給出實(shí)現(xiàn)代碼,需要的朋友可以參考下

Perl中著名的Schwartzian轉(zhuǎn)換，其產(chǎn)生背景主要涉及到排序問(wèn)題:
比如說(shuō)，根據(jù)文件名以字母順序排序，代碼如下:

復(fù)制代碼代碼如下:

use strict;  

use warnings;  

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

my @sorted_files = sort @files;    #sort()，排序，默認(rèn)是字母順序排序

比如說(shuō)，根據(jù)文件名長(zhǎng)度排序，其代碼如下:

復(fù)制代碼代碼如下:

use strict;  

use warnings;  

#length求長(zhǎng)度。 太空船操作符<=>，默認(rèn)變量是$a,$b，返回值為-1,0,1分別表示大于，==，小于。 sort進(jìn)行排序  

my $files = ".xml";  

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

上面的兩種情況，對(duì)很多文件操作來(lái)說(shuō)，速度還不算慢，如果是下面這種情況。
比如說(shuō):要批量比較文件大小，其代碼如下:

復(fù)制代碼代碼如下:

use strict;  

use warnings;  

my @files     = glob "*.xml";     

my @sort_size = sort { -s $a <=> -s $b } @files;  #比較大小

上面的代碼設(shè)計(jì)到三重(次)操作:
1. 從硬盤上獲取文件大小(-s $b)
2. 比較文件大小(太空船操作)
3. 對(duì)其進(jìn)行排序(sort操作)
考慮到要比較$a,$b大小時(shí)，要從硬盤中獲取兩次，所以次數(shù)是6次！也就是說(shuō)，如果有1萬(wàn)個(gè)文件，總共是6萬(wàn)次。
其算法復(fù)雜度是: n*long(n),考慮到后兩項(xiàng)(比較文件大小，進(jìn)行排序)必然要進(jìn)行的操作，但第一項(xiàng)卻可以降低！
即一次性從硬盤中讀取所有文件大小，將其放置到Perl中的默認(rèn)的變量，并存儲(chǔ)到內(nèi)存中！于是又下面算法實(shí)現(xiàn):

復(fù)制代碼代碼如下:

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;

看上去比較復(fù)雜，分三個(gè)步驟解釋下:
第一步:遍歷文件列表，對(duì)每個(gè)文件創(chuàng)建一個(gè)數(shù)組引用。數(shù)組引用包含兩個(gè)元素：
第一個(gè)是文件名($_)，第二個(gè)是文件大小(-s $_)。這樣，處理每個(gè)文件只訪問(wèn)一次磁盤。
第二步:對(duì)二維數(shù)組排序。因比較文件大小，所以需取元素[1]，比較它們的值。得到另一個(gè)二維數(shù)組。
第三步:丟掉文件大小元素，創(chuàng)建一個(gè)只含文件名的列表。完成目標(biāo)!
上面的代碼使用了兩個(gè)臨時(shí)數(shù)組，但這并不是必須的。我們可以一個(gè)語(yǔ)句就能完成所有的工作。為了達(dá)到目的，需要按照“數(shù)據(jù)從右流向左”的原理反轉(zhuǎn)句子順序，不如果將每個(gè)句子放在單獨(dú)一行，并且留出足夠的空間，我們依然可以寫出可讀性高的代碼。

復(fù)制代碼代碼如下:

my @quickly_sorted_files =  

    map  { $_->[0] }  

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

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

    @files;

這就是以Randal L. Schwartz命名的Schwartzian轉(zhuǎn)換，對(duì)數(shù)據(jù)量特多的情況下，其速度要比前者快數(shù)倍！
下面寫了小程序，包括在生成1萬(wàn)個(gè)xml文件，在兩種情況下，完整代碼如下:

復(fù)制代碼代碼如下:

#!/usr/bin/perl -w
use strict;
use warnings;
use autodie;
use v5.10;

######################################
### 創(chuàng)建要比較的10,000個(gè).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";

######################################
### 常規(guī)轉(zhuǎn)換:      遍歷20次       ###
######################################
my $t1 = time();

foreach (1..20){
    my @files     = glob "*.xml";
    my @sorted    = sort { -s $a <=> -s $b } @files;
}

say "常規(guī)算法需要時(shí)間: => ", time()- $t1;

######################################
### Schwartzian轉(zhuǎn)換: 遍歷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算法需要時(shí)間: => ", time()- $t2;

輸出結(jié)果:
All the 10_1000 files created!
常規(guī)算法需要時(shí)間: => 185
Schwartzian算法需要時(shí)間: => 115