hirax.net::inside out::2012年02月21日

最新記事(inside out)へ  |   年と月を指定して記事を読む(クリック!)

2012年1月 を読む << 2012年2月 を読む >> 2012年3月 を読む

2012-02-21[n年前へ]

お気楽・超簡単な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)関数作成テクニック」を使ってみると、きっと驚くほどの高速化が実現できるはずです。