読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Memoizeの話

土曜日の弾さんの講演会で, Memoizeというモジュールの存在を初めて知ったのでまとめておきます.

参考

この記事を書くにあたり, 以下のサイトを参考にしました:
http://floralcompany.jp/archives/2008/07/use-memoize.html
http://d.hatena.ne.jp/cooldaemon/20060313/1142215135

メモ化

Memoizeを使うことで, サブルーチンを呼び出した際の結果を記憶しておくことができます.
これによって, その関数が再び呼び出された時に再計算することを防ぎ, 処理を高速化することができます.

ちなみに, こういう最適化手法をメモ化と言うらしいです.

例: フィボナッチ数

メモ化が有効なパターンを見てみましょう. まあ, 弾さんが紹介していたモノと同じなのですが...

フィボナッチ数を計算するスクリプトを, 定義に従ってPerlで書いてみると, こんな感じになります.

use strict;
use warnings;

my $input = $ARGV[0];
print "f($input) = " . fib($input) . "\n";

sub fib {
    my $n = shift;
    return 0 if $n == 0;
    return 1 if $n == 1 || $n == 2;
    return fib($n-1) + fib($n-2);
}

実行してみるとわかりますが, 入力値が30前後になると極端に遅くなってしまいます.
これは, 入力値がnのとき, 関数fibが2*fib(n)-1回呼び出されてしまうのが原因です.

こうするとわかりやすくなります.

use strict;
use warnings;

my $input = $ARGV[0];
my $call = 0;

print "f($input) = " . fib($input) . "\n";
print "called = $call\n";

sub fib {
    my $n = shift;
    $call++;

    return 0 if $n == 0;
    return 1 if $n == 1 || $n == 2;
    return fib($n-1) + fib($n-2);
}

実行してみましょう.

$ perl fib.pl 5
f(5) = 5
called = 9
$ perl fib.pl 10
f(10) = 55
called = 109
$ perl fib.pl 20
f(20) = 6765
called = 13529
$ perl fib.pl 30
f(30) = 832040
called = 1664079

フィボナッチ数はnが増えると爆発的に増えていくので, 関数fibを呼び出す回数も同様に増えていき, 実行時間が遅くなっているのです.

メモ化

こういう場合に有効なのがメモ化です.
言うまでもありませんが, ある数字nのフィボナッチ数は不変です.
つまり, 1度計算しておけば, 後は使いまわせるということです.

というわけで, 先ほどのコードを書き換えてみます.

use strict;
use warnings;

my $input = $ARGV[0];
my $call = 0;
my @memoize;

print "f($input) = " . fib($input) . "\n";
print "called = $call\n";

sub fib {
    my $n = shift;

    return $memoize[$n] if defined $memoize[$n];

    $call++;

    return $memoize[$n] = 0 if $n == 0;
    return $memoize[$n] = 1 if $n == 1 || $n == 2;
    return $memoize[$n] = fib($n-1) + fib($n-2);
}

配列memoizeを用意して, 関数fibの引数$nに対して$memoize[$n]が存在するなら, それをそのまま返します.
そうでないなら計算して, $memoize[$n]に格納していきます.

こうすることで, 実行時間(つまり関数fibの呼び出し回数)は劇的に短くなります.

$ perl fib.pl 5 
f(5) = 5
called = 5
$ perl fib.pl 10
f(10) = 55
called = 10
$ perl fib.pl 20 
f(20) = 6765
called = 20
$ perl fib.pl 30
f(30) = 832040
called = 30

Memoize

この処理を簡単に(メモ化の処理を意識せずに)してくれるモジュールが, Memoizeになります.
先ほどのスクリプトを, Memoizeを使って書きなおしてみます.

use strict;
use warnings;
use Memoize;

memoize('fib');

my $input = $ARGV[0];
my $call = 0;

print "f($input) = " . fib($input) . "\n";
print "called = $call\n";

sub fib {
    my $n = shift;
    $call++;

    return 0 if $n == 0;
    return 1 if $n == 1 || $n == 2;
    return fib($n-1) + fib($n-2);
}

memoize('fib')でメモ化する関数を指定すれば, 後はMemoizeモジュールがよしなに処理してくれます.

$ perl fib.pl 5 
f(5) = 5
called = 5
$ perl fib.pl 10
f(10) = 55
called = 10
$ perl fib.pl 20 
f(20) = 6765
called = 20
$ perl fib.pl 30
f(30) = 832040
called = 30

メモ化が使えない場合

メモ化が使えない場合も, もちろんあります.
例えば, 関数内に副作用があって, 関数のある引数とその返り値が一定で場合, メモ化は使えません.

use strict;
use warnings;

my $input = $ARGV[0];
my $total = 0;

$total = func($_) for 1..10;
print $total . "\n";
$total = func($_) for 1..10;
print $total . "\n";

sub func {
    my $n = shift;

    return $n + $total;
}

綺麗な例ではないので申し訳ないのですが...
関数funcは, 引数と返り値が常に一定ではありません. 外にある変数$totalの値次第で変わってしまいます.
例えば, 引数$nが0で$totalが0なら返り値は0になりますが, $totalが100なら100になります.

こういう場合にMemoizeを使ってメモ化をすると, 意図しない動作(メモ化する場合とそうでない場合で結果が変わってしまう)が起きてしまいます. 気をつけましょう.

まとめ

Memoizeモジュールについてまとめてみました.
「お仕事」よりは「研究」のような場面で使い道がありそうですね!
最近のPerlならデフォルトで入っているので, 「スクリプトの処理が遅すぎて...」という場合, メモ化できる部分がないか探してみるのもアリかなーと思います.

余談ですが, 最初ずっとMemonizeだと思っていました...