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 語言中，|| 只會傳回 0 或 1（false 或 true），然而在 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