在 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; } } );我拿了兩萬多個檔案來測試,結果如下:
執行效率在這個例子來看是相差 3.8 倍,但理論上檔案數量越多,差異會越大。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)
參考資料:Effective Perl Programming、Perl Paraphernalia
沒有留言:
張貼留言