メモ化

[hysryt]

最適化手法の一つ。 負荷の高い関数呼び出しの回数を減らすためのテクニック。 一言で言うと入力値に対する戻り値をキャッシュすること。

例えば負荷の高い関数 funcA() があるとする。

funcA(10);  // 1秒かけて処理を行う。

2回繰り返せば当然2倍の時間がかかる。

funcA(10);  // 1秒かけて処理を行う。
funcA(10);  // さらに1秒かけて処理を行う。

ここで、一度計算した値をキャッシュしておき、入力値が同じ場合はキャッシュから値を返すようにすれば無駄な計算がなくなり処理が速くなる。

func(10);  // 1秒かけて処理を行う。
func(10);  // 即座にキャッシュから値を返す。

最初の1回は通常の処理の時間がかかるが、2回目以降は時間を短縮できる。

キャッシュに値がない場合は当然時間がかかる。

func(10);  // 1秒かけて処理を行う。
func(100);  // 1秒かけて処理を行う。

また、関数の戻り値が入力値以外に依存する場合は使えないので注意が必要。

https://dev.to/nas5w/an-introduction-to-memoization-59o