計算の工夫

依存グラフとキャッシュの管理

一番基本的な工夫は、状態間の依存関係を管理して、ある状態が変化したとき、その状態に依存する状態だけについて
再計算を行うことです。
a = 1
b = 2
c = 3
d = a + b
e = d * c
の依存グラフはこんなかんじになります。

たとえばc = 5となった場合は、dは影響を受けないので
eだけを再計算すればよいことになります。
これを効率よく計算するには、dの値をキャッシュしておく必要があります。
そうでなければ、dの計算もやり直す必要がでます。
もうひとつの方法は、eの値をキャッシュしておいて、
e_new = e_old / c_old * c_new
を計算することです。
こちらの方法は、値が浮動小数点の場合は丸め誤差がでるため、そのままでは使えないなど
より面倒です。
どちらの方法をとるにせよ、依存グラフとキャッシュを管理することで、計算量を減らすのが、
もっとも基本的な方法になります。

差分計算

もうひとつの工夫は、依存グラフにそって、変更の差分だけを伝えることです。

例えば、次のように整数のリストと、その合計値を定義したとします。
xs = [1,2,3,4]
y = sum(xs)
ここで、リストに対して要素を追加した場合、
追加された要素の情報だけを伝播させれば、
sum(xs)の値を更新することができます。

計算の先延ばし

もうひとつの方法は遅延評価を行うことです。
ある状態が更新しても、その値をすぐに使う必要が無い場合は、
その値が必要とされるときまで、再計算を先延ばしにすることで、無駄な計算を省くことができます。