以前HTML5プロフェッショナル認定試験の勉強をしている際にメモ化というワードが出てきました。
その時に軽くだけ調べると
どうやら関数型プログラミングで使用されるもののようで。
今回はもう少し詳しく調べ、まとめてみました。
メモ化とは
Wikipediaには下記のように記述されています。
メモ化とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出しごとの再計算を防ぐ手法である。
キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。
なるほど。
メモ化はキャッシュに含まれるのですね。
では実際、どのように使用するのか見ていきましょう。
メモ化の使用例
フィボナッチ数列の計算を例に見てみましょう。
フィボナッチ数列とは、
隣り合う2つの数字の和が次の数字になるという法則を持つ数列です。
次の漸化式で定義されます。
\begin{flalign}
&\quad F_0 = 0& \\
&\quad F_1 = 1& \\
&\quad F_n = F_{n-1} + F_{n-2} \quad (n \geq 2)&
\end{flalign}
0 ～ 15項は次の通り
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …
メモ化を使用しない場合
この場合、同じnの値に対して何度も再帰的に計算を繰り返すため、
計算量が多くなってしまいます。
function fibonacci(n) {
if(n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(40));
メモ化を使用する場合
memoというオブジェクトを使用し、
一度計算した結果をキャッシュしておき、
再度同じ引数で関数が呼ばれた場合にキャッシュから結果を取り出します。
function fibonacci(n, memo = {}) {
if(n in memo) return memo[n]; // キャッシュから結果を取得
if(n <= 1) return n;
// 計算結果をキャッシュ
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
console.log(fibonacci(40));
時間の計測
JavaScript Playground で処理時間を比較してみました。
■メモ化を使用しない場合
■メモ化を使用する場合
環境等にも依存しますが、こう比べるとかなり違いますね。
まとめ
計算コストの高い関数の実行結果をキャッシュして再利用することで、
パフォーマンスを向上させるテクニックのようです。
メモ化によって、同じ入力で関数が再度呼ばれたときにキャッシュされた結果を返すことで
計算時間を節約できるため、再帰関数や大規模データセットの処理でより有効そうですね。
ただし、キャッシュが大きくなるとメモリを多く消費するので
そこには注意が必要かと思います。
それでは。
参考文献