今回は「たらいまわし関数」を例題にして、「メモ化」と「遅延評価」について説明します。
最初に「たらいまわし関数」について説明します。次のリストを見てください。
リスト : たらいまわし関数
sub tarai {
my ($x, $y, $z) = @_;
if ($x <= $y) {
$y;
} else {
tarai(tarai($x - 1, $y, $z), tarai($y - 1, $z, $x), tarai($z - 1, $x, $y));
}
}
sub tak {
my ($x, $y, $z) = @_;
if ($x <= $y) {
$z;
} else {
tak(tak($x - 1, $y, $z), tak($y - 1, $z, $x), tak($z - 1, $x, $y));
}
}
関数 tarai や tak は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。
関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄氏によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 氏によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。
リスト : たらいまわし関数の実行 use strict; use warnings; use Time::HiRes; # # 関数定義は省略 # my $s = Time::HiRes::time; print tarai(12, 6, 0), "\n"; print Time::HiRes::time - $s, "\n"; $s = Time::HiRes::time; print tak(18, 9, 0), "\n"; print Time::HiRes::time - $s, "\n";
Time::Hires は高精度の時刻やタイマーに関する関数を提供するモジュールです。Perl の関数 time は 1970 年 1 月 1 日 UTC からの秒数を返しますが、Time::Hires::time は小数点数 6 桁 (ナノ秒) まで計測します。
それでは実行してみましょう。
$ perl tarai.pl 12 2.81726503372192 9 3.55909490585327 実行環境 : Perl v5.34.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数が遅いのは、同じ値を何度も計算しているためです。この場合、表 (table) を使って処理を高速化することができます。同じ値を何度も計算することがないように、計算した値は表に格納しておいて、2 回目以降は表から計算結果を求めるようにします。このような手法を「表計算法」とか「メモ化 (memoization または memoisation)」といいます。
ハッシュを使うと、たらいまわし関数のメモ化は次のようになります。
リスト : たらいまわし関数のメモ化 (1)
use strict;
use warnings;
use Time::HiRes;
# メモ用のハッシュ
our %table = ();
sub tarai {
my ($x, $y, $z) = @_;
my $key = "$x $y $z";
if (!$table{$key}) {
$table{$key} = $x <= $y ? $y : tarai(tarai($x - 1, $y, $z),
tarai($y - 1, $z, $x),
tarai($z - 1, $x, $y));
}
$table{$key};
}
my $s = Time::HiRes::time;
print tarai(12, 6, 0), "\n";
print Time::HiRes::time - $s, "\n";
関数 tarai の値を格納するハッシュを大域変数 %table に用意します。関数 tarai では、引数 $x, $y, $z を文字列 "$x $y $z" に変換し、それをキー ($key) にして %table を検索します。%table に $key があればその値を返します。そうでなければ、tarai を計算して %table にセットし、その値を返します。
それでは実行してみましょう。
$ perl tarai_memo.pl 12 0.000413179397583008 実行環境 : Perl v5.34.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
とても速くなりましたね。
このように関数をメモ化することは簡単にできますが、メモ化を行うたびに関数を修正するのは面倒です。このような場合、関数をメモ化する「メモ化関数」があると便利です。Perl の場合、モジュール Memoize を使うと簡単に関数をメモ化することができます。
プログラムは次のようになります。
リスト : Memoize によるメモ化 (tarai1.pl)
use strict;
use warnings;
use Memoize;
use Time::HiRes;
sub tarai {
my ($x, $y, $z) = @_;
if ($x <= $y) {
$y;
} else {
tarai(tarai($x - 1, $y, $z), tarai($y - 1, $z, $x), tarai($z - 1, $x, $y));
}
}
sub tak {
my ($x, $y, $z) = @_;
if ($x <= $y) {
$z;
} else {
tak(tak($x - 1, $y, $z), tak($y - 1, $z, $x), tak($z - 1, $x, $y));
}
}
# メモ化
memoize('tarai');
memoize('tak');
my $s = Time::HiRes::time;
print tarai(12, 6, 0), "\n";
print Time::HiRes::time - $s, "\n";
$s = Time::HiRes::time;
print tak(18, 9, 0), "\n";
print Time::HiRes::time - $s, "\n";
メモ化は簡単です。memoize('関数名') でメモ化する関数を指定するだけです。
それでは実際に実行してみましょう。
$ perl tarai1.pl 12 0.00148510932922363 9 0.00447702407836914 実行環境 : Perl v5.34.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
メモ化の効果は十分に出ていると思います。また、同じ計算を再度実行すると、メモ化の働きにより値をすぐに求めることができます。
関数 tarai は「遅延評価 (delayed evaluation または lazy evaluation)」を行う処理系、たとえば関数型言語の Haskell では高速に実行することができます。また、Scheme でも delay と force を使って遅延評価を行うことができます。
tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。
完全ではありませんが、Perl でもクロージャを使って遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
use strict;
use warnings;
use Time::HiRes;
sub tarai {
my ($x, $y, $z) = @_;
if ($x <= $y) {
$y;
} else {
my $zz = $z->();
tarai(tarai($x - 1, $y, sub { $zz }),
tarai($y - 1, $zz, sub { $x }),
sub { tarai($zz - 1, $x, sub { $y }); });
}
}
my $s = Time::HiRes::time;
print tarai(12, 6, sub { 0 }), "\n";
print Time::HiRes::time - $s, "\n";
遅延評価したい処理をクロージャに包んで引数 $z に渡します。そして、$x > $y のときに引数 $z の関数を呼び出します。すると、クロージャ内の処理が評価されて $z の値を求めることができます。たとえば、sub { 0 } を $z に渡す場合、$z->() とすると返り値は 0 になります。sub { $x } を渡せば、$x に格納されている値が返されます。sub { tarai( ...); } を渡せば、関数 tarai が実行されてその値が返されるわけです。
それでは、実際に実行してみましょう。
$ perl tarai_clo.pl 12 0.000205039978027344 実行環境 : Perl v5.34.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
メモ化よりも速くなりました。tarai 関数の場合、遅延評価の効果はとても大きいですね。ところで、クロージャを使わなくても tarai 関数を高速化する方法があります。C++:language&libraries (cppll) [リンク切れ] で Akira Higuchi さんが書かれたＣ言語の tarai 関数はとても高速です。Perl でプログラムすると次のようになります。
リスト : tarai 関数の遅延評価 (2)
use strict;
use warnings;
use Time::HiRes;
sub tarai_lazy {
my ($x, $y, $xx, $yy, $zz) = @_;
if ($x <= $y) {
$y;
} else {
my $z = tarai($xx, $yy, $zz);
tarai_lazy(tarai($x - 1, $y, $z), tarai($y - 1, $z, $x), $z - 1, $x, $y);
}
}
sub tarai {
my ($x, $y, $z) = @_;
if ($x <= $y) {
$y;
} else {
tarai_lazy(tarai($x - 1, $y, $z), tarai($y - 1, $z, $x), $z - 1, $x, $y);
}
}
my $s = Time::HiRes::time;
print tarai(12, 6, 0), "\n";
print Time::HiRes::time - $s, "\n";
関数 tarai_lazy の引数 $xx, $yy, $zz で $z の値を表すところがポイントです。つまり、$z の計算に必要な値を引数に保持し、$z の値が必要になったときに tarai($xx, $yy, $zz) で計算するわけです。
それでは実行してみましょう。
$ perl tarai_lazy.pl 12 0.0001068115234375
Perl でも高速に実行することができました。このような簡単な方法で tarai 関数を高速化できるとは驚きました。Akira Higuchi さんに感謝いたします。