萬盛學電腦網

 萬盛學電腦網 >> 網絡編程 >> 編程語言綜合 >> Perl中著名的Schwartzian轉換問題解決實現

Perl中著名的Schwartzian轉換問題解決實現

   這篇文章主要介紹了Perl中著名的Schwartzian轉換問題解決實現,本文詳解講解了Schwartzian轉換涉及的排序問題,並同時給出實現代碼,需要的朋友可以參考下

  Perl中著名的Schwartzian轉換,其產生背景主要涉及到排序問題:

  比如說,根據文件名以字母順序排序,代碼如下:

   代碼如下:

  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;

  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],比較它們的值。得到另一個二維數組。

  第三步:丟掉文件大小元素,創建一個只含文件名的列表。完成目標!

  上面的代碼使用了兩個臨時數組,但這並不是必須的。我們可以一個語句就能完成所有的工作。為了達到目的,需要按照“數據從右流向左”的原理反轉句子順序,不如果將每個句子放在單獨一行,並且留出足夠的空間,我們依然可以寫出可讀性高的代碼。

   代碼如下:

  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;

  }

  say "Schwartzian算法需要時間: => ", time()- $t2;

  輸出結果:

  All the 10_1000 files created!

  常規算法需要時間: => 185

  Schwartzian算法需要時間: => 115

copyright © 萬盛學電腦網 all rights reserved