0

私は C# でアイデアをいじっています。グラフ内の多数のノードを非同期的に更新する最善の方法についてアドバイスをお願いします。そのようなことを行う方法については何も読んでいません。教科書/例で見たものはすべて、ノードが実際には変化しないグラフを使用しています。

多数のノード (数千) のグラフがあるとします。各ノードには、それぞれの隣接ノードのいくつかのパブリック プロパティに依存するいくつかの内部状態と、場合によってはいくつかの外部入力があります。

したがって、ノードは単純に次のようになります。

class Node
{
    State internalState;
    public State exposedState;

    Input input;
    List<Node> neigbors;        

    void Update()
    {
        while (true)
        {
            DoCalculations(input, internalState, neighbors);
            exposedState = ExposedState(internalState);
        }
    }

    State ExposedState(State state) { ... }
    void DoCalculations() { ... }
}

難しいのは、ノードの入力状態が (イベントのサブスクライブまたはポーリングによって) 変化するか、隣接ノードの状態が変化するとすぐにノードを更新したいということです。これを単純な方法で同期的に実行しようとすると、明らかな問題が発生します。

Node A updates when input changes
Its neighbor B sees A has changed, updates.
Node A sees its neighbor B has changed, updates
B updates
A updates
....
Stack overflows

代わりに、すべてのノードを列挙してそれらの更新メソッドを呼び出して更新すると、ノードが一貫して更新されない可能性があります (例: A の入力が変更され、B が更新され、A の変更が表示されず、A が更新され、公開された状態が変更されます)。

最初に更新したいノードのスタックを維持しようとすることで更新できますが、次にそれらの隣接ノードを更新する必要があり、次にそれらのノードを更新する必要があります。つまり、更新サイクルごとに慎重にグラフを調べて、正しい更新順序、非常に遅くなる可能性があります...

素朴な非同期の方法は、各ノードを独自のスレッドに持つことです (または、より簡単に言えば、最初の非同期メソッド呼び出しが各ノードの update メソッドに対して発生し、while(true){...} で無期限に更新されます)。彼の問題は、何千ものスレッドを持つことは良い考えとは思えないことです!

これには簡単な解決策があるはずです。これはセルオートマトンとそれほど違いはありませんが、私が思いついた同期ソリューションは、一方の端から他方の端までメッセージを取得するためにノードの数と比較して多数回更新する必要があるか、ある種の複雑な問題を解決する必要があります複数の開始点を持つグラフ ウォーキング問題。

非同期メソッドは、数千のスレッドを持つことができれば、自明に単純に思えます...

では、このようなことを行うための最良の方法は何ですか?

4

2 に答える 2

1

Rx ( The Reactive Extensions ) が良い出発点になると思います。

他のノードが依存する必要がある可能性のある状態の各部分は として公開され、IObserable<TState>他のノードはそれらのオブザーバブルにサブスクライブできます。

otherNode.PieceOfState.SubScribe(v => { UpdateMyState(v) });

Rx は、オブザーバブルに対して多くのフィルタリングおよび処理機能を提供します。これらは、重複するイベントをフィルタリングするために使用できます (ただし、もちろん「重複」を定義する必要があります)。

ここに紹介記事があります: http://weblogs.asp.net/podwysocki/archive/2009/10/14/introducing-the-reactive-framework-part-i.aspx

于 2012-05-13T09:36:35.993 に答える
0

まず、更新が収束することを確認する必要があります。これは、それらの実行方法（同期、非同期、シリアル、または並列）とは関係ありません。

接続である2つのノードAとBがあるとします。Aが変更され、Bの再計算がトリガーされます。次にBが変更され、Aの再計算がトリガーされます。Aの再計算によってAの値が変更されると、Bの再計算がトリガーされます。この一連のトリガーを1つのポイントで停止する必要があります。つまり、変更を収束させる必要があります。そうでない場合、使用する手法で修正することはできません。

計算が収束し、無限の再計算に陥らないことを確認したら、単純なシングルスレッド同期計算から始めて、それがうまく機能するかどうかを確認する必要があります。十分に速い場合は、そこで停止します。そうでない場合は、並列化を試みることができます。

計算ごとにスレッドを作成することはありません。スケーリングはまったく行われません。代わりに、実行する必要のある計算のキューを使用し、ノードAの値を変更するたびに、そのすべてのネイバーをキューに入れます。キューを処理するスレッドをいくつか持つことができるため、キューははるかにスケーラブルなアーキテクチャになります。

それでも十分な速度が得られない場合は、キューに入れるものとその処理方法を最適化する必要があります。今それを心配するのは時期尚早だと思います。

于 2012-05-13T10:24:46.807 に答える