シュワルツ変換

一番最初に「シュワルツ変換」という名前を聞いたとき、「かっこいい〜使いたい」と思いました。

〜シュワルツ変換とはなんなのか〜

• 使う場面を簡単にいうとこんな感じでしょうか。
  • 何かソートしたいリストがある。
  • ソートの条件となる値はリストの値を加工して取得する必要がある。
  • その加工する処理が重めである。

そのままsort関数でやると、コードとしては見やすいのですが、ソート用に加工する処理を無駄に何度も実行してしまい、時間がかかるので、必要最低限の回数のみだけ加工処理を行おうというのがシュワルツ変換です。

「続・初めてのPerl」で通常のソートと、シュワルツ変換のベンチマークを取れという問題があったのでやってみました。

→/bin/以下のファイルのリストを取得し、-sで取得したサイズをもとにソートし、結果のリストを取得しています。

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark;
my @bin_list = glob "/bin/*";
my $count = -5; 
# 一般的なソート処理
sub normal {
    my @sorted = sort { -s $a <=> -s $b } @bin_list;
}
# シュワルツ変換
sub schwartz {
    my @sorted = 
    map $_->[0],
    sort {$a->[1] <=> $b->[1]}
    map [$_, -s $_],
    @bin_list;
}
timethese $count, {'normal' => '&normal', 'schwartz' => '&schwartz'};

結果です。

koba04% perl schwartz.pl
Benchmark: running normal, schwartz for at least 5 CPU seconds...
    normal:  5 wallclock secs ( 1.68 usr +  3.63 sys =  5.31 CPU) @ 144.44/s (n=767)
  schwartz:  5 wallclock secs ( 3.88 usr +  1.36 sys =  5.24 CPU) @ 517.56/s (n=2712)

5秒間実施させた時、シュワルツ変換は2712回、通常のソートは767回で、約3倍ちょっと多く処理を実行出来ています。

コードの見やすさは通常のソートが勝りますが、場面に応じて使用したいテクニックだと思いました。

それにしても、「続・初めてのPerl」は本当にいい本だと思います。
一通りは読み終わったのですが、練習問題がまだなので、それを全部やり終わったら感想を書きたいと思います。