hirax.net::Keywords::「メモ化」のブログ

■お気楽・超簡単なMathematicaのメモ化（memoization）関数作成テクニック　

　Mathematicaは数式処理を行うためのシステムをLISP風に実装したような「プログラミング言語」です。「Mathematicaにおけるプログラムの高速化手法）」は色々ありますが、今日書くのは「お気楽・超簡単な、Mathematicaのメモ化（memoization）関数作成テクニック」です。

　メモイズ（メモ化＝memoization）は、呼び出し時引数と結果をキャッシュし、次回呼び出し時の再計算を不要にする」というテクニックです。膨大な回数の計算を行うように見えて、それらの計算の中で「何回も同じ計算（＝引数が同じ関数の呼び出し）」が行われている場合、メモ化を行えば処理時間を大幅に短縮することができます。

　「お気楽・超簡単なMathematicaのメモ化（memoization）関数作成テクニック」は、たったこれだけ（のコード）です。

hoge[x_] := hoge[x] = f(x)

　つまり、（たとえば）xを引数に持つ関数hoge[x]の遅延評価呼び出しで宣言しつつ、「遅延評価が行われた際には、その引数による計算をした上で、その計算結果で（呼び出し引数）に対する関数の”（即時）定義”を行う処理を行うように書く」ことで、「呼び出し時引数と結果をキャッシュする関数」を定義することができる、というわけです。

　たとえば、フィボナッチ数列を計算する関数fib[x]を、こんな風に書くと、

fib[1] = 1;
fib[2] = 1;
fib[n_] := fib[n - 1] + fib[n - 2]

fib[100] を計算するのには、耐えきれないほどの時間が掛かってしまいます。しかし、もしも、こんな風に書いたなら、

fib[1] = 1;
fib[2] = 1;
fib[n_] := fib[n] = fib[n - 1] + fib[n - 2]

fib[100]の計算結果は一瞬で"354224848179261915075"と表示されるはずです。

　Mathematicaは関数（というかシンボル）呼び出し時は、常に引数に「パターンマッチング」を行った上で、「（パターンマッチングの結果に応じて）どのような処理を行うか・どのような値を返すか」を行うかを判断・切り替えます。そのため、上記のようなコードを書くだけで、関数の引数に応じて計算を行ったりキャッシュ値を返したり…という処理を（いともたやすく）実装することができるのです。

　「（膨大な回数の計算を行うように見えて）実は何回も同じ計算をする」という処理をMathematicaで書く場合には、こんな「お気楽・超簡単なMathematicaのメモ化（memoization）関数作成テクニック」を使ってみると、きっと驚くほどの高速化が実現できるはずです。