オブジェクト間のカスケード関係を継続的に計算するための最良のアプローチ（アルゴリズム）は何ですか？

Question

たとえば、a+b = c c+d = e e+f = g各ノードに変更が加えられます。関連するノードは再計算されます。以下の画像は、私がやろうとしていることの単純な例です。

各オブジェクトの構造は同一です。インプットは、価格が変化するごとに価格になり、下流の価格にカスケード効果があります。したがって、上記の例では、a+b = cは5+6 = 11になります。等

変更は絶えず（おそらく毎秒）行われます。各値が変更されると、通知する必要があります（イベントが発射されます）。

Answer 1

グラフが変更されていない限り、値だけができます。 トポロジーの種 あなたのグラフの。次に、変化した値から始まるトポロジーソートオーダーのグラフを歩きます。変更がグラフのまばらな部分になる場合は、各ノードをトポロジーソート順序でインデックスに割り当て、 優先キュー 次にどのノードを行うかを決定します。

Answer 2

最も単純な方法は、JSUTがイベントベースの方法になるでしょう。各ノードには「onChanged」イベントがあり、そのノードを使用するものはすべて、そのイベントを購読できます。ノードがそれ自体を更新した後、それはそのイベントを提起し、知る必要がある他のことを可能にします。

あなたの依存関係がより複雑な場合、あなたは物事を最適化するために更新を管理する何か他のものを持っている必要があるかもしれません。たとえば、効果がBとCとCにも影響を与える場合（例：B = A+CおよびC = A+1）、単純な方法でA、B、C、次にBを更新する可能性があります。これは機能しますが、明らかに必要以上に1つのMROEアップデートです。更新を最適化する正確な方法は、依存ツリーの複雑さによって異なります。