シュワルツ変換の実行効率

続・初めてのPerl の p.113 にシュワルツ変換というものが紹介されていた。

このシュワルツ変換を使うと、sort関数の間接指定内で割高な処理（比較的多くの時間やメモリがかかる処理）をするときに実行効率がよくなるらしい。

例えば、以下の「間接指定内で割高な処理を行う」2つのソート方法では「シュワルツ変換を使ったソート」の方が実行が早くなるということだ。

シュワルツ変換を使ったソート

my @output_data = map $_->[0],
                  sort {$a->[1] と $b->[1] を使ったソート比較}
                  map [$_, $_ の割高な処理],
                  @input_data;

通常のソート

my @output_data = sort {$a の割高な処理と $b の割高な処理 を使ったソート比較}
                  @input_data;

そこで、実際に実行速度に違いが出るのかそれぞれの方法のベンチマークをとって比べてみた。ここでの「割高な処理」としては、長い文字列の処理（大文字への変換）を使った。

#!/usr/bin/perl
use strict;
use warnings;

use Benchmark;

my $loop_count = 50_000;
my $string_count = 1; # この値を変えて実験する
my @castaways = ("skipper" x $string_count,
                  "gilligan" x $string_count,
                  "professor" x $string_count,
                  "ginger" x $string_count,
                  "mary_ann" x $string_count,
              );

# 大文字と小文字を区別しないソート同士の実行速度を比べる
timethese ($loop_count,
           {
             schwartz_sort => sub {
               # シュワルツ変換を使った方法
               my @output_data = map $_->[0], sort {$a->[1] cmp $b->[1]} map [$_, "\U$_"], @castaways;
             },
             normal_sort => sub {
               # 普通のやり方
               my @output_data = sort {"\U$a" cmp "\U$b"} @castaways;
             },
           }
       );

測定結果

表1．「$loop_count = 5000; $string_count = 1000;」のとき

	1	2	3
シュワルツ変換 [sec]	41	38	43
普通のやり方 [sec]	51	47	51

この場合、平均 9 [sec] シュワルツ変換を使った方法が早かった。

表2．「$loop_count = 5000; $string_count = 500;」のとき

	1	2	3
シュワルツ変換 [sec]	17	17	17
普通のやり方 [sec]	25	25	26

この場合、平均約8 [sec] シュワルツ変換を使った方法が早かった。

表3．「$loop_count = 5000; $string_count = 100;」のとき

	1	2	3
シュワルツ変換 [sec]	6	6	6
普通のやり方 [sec]	7	7	7

この場合、平均 1 [sec] シュワルツ変換を使った方法が早かった。

表4．「$loop_count = 5000; $string_count = 1;」のとき

	1	2	3
シュワルツ変換 [sec]	4	4	4
普通のやり方 [sec]	2	2	2

この場合、平均 2 [sec] 普通のやり方を使った方法が早かった。

うーん、この結果を見ると、確かに長い文字列（4000文字前後くらいかな？）ではシュワルツ変換を使った方法の方が効率がよかったみたいだ。

ちなみに、ここには載せなかったけど、ソート対象の配列の要素数が少ないと（今回の場合は @castaways の要素数が少ないと）、シュワルツ変換を使ったやり方の方が常に効率が悪いみたい。例えば、以下のように要素数2 で試してみると分かる。

my @castaways = ("skipper" x $string_count,
                  "gilligan" x $string_count,
                );

かなり大雑把な測定しかしてないけど、結論としては、めちゃくちゃ長い文字列を sort の間接指定で比較するときはシュワルツ変換を使うのが正しい方法ということかな。とりあえず、「続・初めてのPerl p113 の脚注2」の意味するところがなんとなく分かったからよしとしておく。

参考

ベンチマーク - Perl表技集：Perlでのベンチマークのやり方を参考にした
続・初めてのPerl p113 の脚注2