パフォーマンス最適化とかで出てくるメモ化（memoization）とはなにか？
はじめに
メモ化というワードをちょいちょい聞いていたのですが、パフォーマンスを上げるための仕組みとか、キャッシュを使うとかそんな印象程度しか知らなかったので、ちゃんと調べて理解していきたいと思います。
メモ化とは
Wikipedia では以下のように記しています。
メモ化（英: Memoization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。
ちょっとまだよくわからないが、メモ化とは 「プログラムを高速化させるための技法」 ということはわかった。
Wikipedia の同じページの概要の一部を引用。
メモ化された関数は、以前の呼び出しの際の結果をそのときの引数と共に記憶しておき、後で同じ引数で呼び出されたとき、計算せずにその格納されている結果を返す。メモ化可能な関数は参照透過性を備えたものに限られる。すなわち、メモ化されたことで副作用が生じない場合に限られる。
ここを見ると、1 回呼び出した関数の結果をキャッシュか何かで記憶（保存）しておいて、2 回目以降で使用される時に、関数を再度実行するのではなく記憶しておいた結果を返すということのよう。
ただし副作用が生じる場合は使用できない。参照透過性を備えた関数にしかメモ化できないと記載しているが、そもそも参照透過性とはなんだ。
参照透過性とは
参照とかってワードはよく聞くが、ここも曖昧なのでちゃんと調べる。
- 参照透過性
- 引数が同じであれば常に同じ結果を返すこと
- 関数の評価結果が状態変化の副作用に左右されることがない
- 副作用
- グローバル変数の変更など、外部の影響を受けて状態に変化を起こす作用のこと
- 「引数から計算して値を返す」（主作用）以外の作用
参照透過性と副作用は反対の意味っぽいけど、性質と作用の話だから若干違いそう。
参考
まとめ
メモ化とは関数の計算結果を保存しておくことによって、 「プログラムを高速化させるための技法」。
ただし、メモ化可能な関数は引数が同じであれば常に同じ結果を返すような参照透過性を備えた関数に限られる。（副作用がある関数はメモ化できない）
Discussion