Orcish Maneuver:讓 Perl 排序程式加速的方法

Orcish Maneuver 是一個可以讓 Perl 排序程式加速的實作方式,這個方法在法則的排序問題上非常有用。


在 Perl 程式中,如果遇到比較複雜的排序問題時,一般的程式設計師會會使用 sort 配合一個自己撰寫的排序函式來處理。

舉例來說,假設我們有一個 @file 陣列,裡面儲存了許多檔案名稱,如果我們想要依照檔案的更改時間來排序,通常會這樣寫:
my @sorted = sort { -M $a <=> -M $b } @files;

其中 -M 會傳回檔案的相對更改時間(請參考 perldoc),然後 sort 再根據這個數值來進行排序。

由於 -M 這個運算子會需要去查詢檔案的更改時間,這個動作是比較費時的,如果檔案數量很多的時候,就容易造成執行速度下降的問題,這時候就可以改用 Orcish Maneuver 的寫法:
my @sorted =
  sort { ( $m{$b} ||= -M $b ) <=> ( $m{$b} ||= -M $b ) }
  @files;
這裡的 ||= 是一個比較少見的運算子,他只是將 ==|| 合起來寫而已,也就是說
$m{$a} ||= -M $a
就等同於
$m{$a} = $m{$a} || -M $a
而這樣的寫法在 sort 第一次遇到某個檔案名稱 $a 時,$m{$a} 會傳回 undef,這時候 || 右方的 -M $a 就會被執行。

如果在 C 語言中,|| 只會傳回 01falsetrue),然而在 Perl 中的 || 運算子會傳回實際執行的結果,所以這時候 -M $a 的執行結果就會儲存至 $m{$a}

如此一來,當下一次在遇到相同的檔案名稱 $a 時,他就可以直接使用 $m{$a} 裡面所儲存的結果,不用再執行一次 -M $a,這樣就可以節省許多不必要的動作。

而這裡的 %m 是一個暫時性的雜湊(hash),在使用前應該要確保它是空的,而且在排序完成之後就沒有用了,所以建議可以這樣寫:
{
  my %m;
  @sorted = sort ...
}
%m 限制在這個範圍(scope)之內。

以下是一個小測試程式,它會將目前目錄中所有的檔案名稱讀進來,然後使用 Perl 的 Benchmark 模組進行兩種寫法的排序測試:
#!/usr/bin/perl
use Benchmark;
@files = <*>;
timethese(0, {
    Ori => sub {
      my @sorted = sort { -M $a <=> -M $b } @files;
    },
    OM => sub {
      my @sorted =
        sort { ( $m{$b} ||= -M $b ) <=> ( $m{$b} ||= -M $b ) }
        @files;
    }
  }
);
我拿了兩萬多個檔案來測試,結果如下:
Benchmark: running OM, Ori for at least 3 CPU seconds...
        OM:  3 wallclock secs ( 3.07 usr +  0.00 sys =  3.07 CPU) @ 43.65/s (n=134)
       Ori:  3 wallclock secs ( 0.85 usr +  2.31 sys =  3.16 CPU) @ 11.08/s (n=35)
執行效率在這個例子來看是相差 3.8 倍,但理論上檔案數量越多,差異會越大。

參考資料:Effective Perl Programming、Perl Paraphernalia
本站已經搬家了,欲查看最新的文章,請至 G. T. Wang 新網站