シャチ泳ぎとシュワルツ変換

今日はちょっと高度なソートについて解説してみるよ。

perl の sort 関数は便利なんだけど、使い方によっては無駄にマシンパワーを使ってしまいます。

ファイルパスが入った @files をファイルテスト演算子 -M でそのファイルが変更されてからの日数で比較してソートしてみます。

my @sorted = sort { -M $a <=> -M $b } @files;

この方法で期待した通りの結果が出ると思いますが、sort 関数で比較されるときに都度 -M で変更されてからの日数を取得しているのが少し無駄です。

そこでシャチ泳ぎ（Orcish Maneuver）という方法で変更してからの日数をキャッシュしながらソートしてみます。

my %m; # キャッシュを溜めておくハッシュ
my @sorted = sort {
    ($m{$a} ||= -M $a) <=> ($m{$a} ||= -M $a)
} @files;

こうすると、一度 -M した結果は %m にあるので毎回 -M で変更された日時を取らずに済みます。

$m{$a} ||= -M $a;
$m{$a} = $m{$a} || -M $a;

この二つは同じ事です。

$m{$a} があれば $m{$a} が、無ければ -M $a が入ります。

余談ですが、このキャッシュの方法はオブジェクトの生成などでもよく見かける方法です。

$self->{ua} ||= LWP::UserAgent->new;

話をソートに戻しましょう。次はシュワルツ変換という方法です。

my @sorted_files
    = map   { $_->[0] }             # 3
      sort  { $a->[1] <=> $b->[1] } # 2
      map   { [ $_, -M ] }          # 1
      @files;

シュワルツ変換は下から順に読んでいく事が出来ます。

1. ファイル名と変更日数の無名配列を作り、配列にして返す
2. 変更日数をキーにソート
3. ファイル名だけの配列を返す

シュワルツ変換は sort する前にあらかじめ計算しておき、sort 時に無駄な計算が発生しないようになります。

perl のコードで表現しなおすとこんな感じですね。

my @files_and_ages = map { [ $_, -M ] } @files;
my @sorted_files_and_ages
    = sort { $a->[1] <=> $b->[1] } @files_and_ages;
my @sorted_files = map { $_->[0] } @sorted_files_and_ages;

それぞれの段階で Data::Dumper するとわかりやすいかも。

参考： Effective Perl p61-63

少し古い本ですが、Perl の中級、上級を目指す人にはいい本ですよ。