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 更新并更改暴露状态）。

我可以通过尝试维护一堆首先要更新的节点来进行更新，但是接下来需要更新他们的邻居，然后再更新他们的，等等，这意味着每个更新周期我都需要仔细遍历图表并确定正确的更新顺序，这可能会很慢......

天真的异步方法是让每个节点都在自己的线程中（或者更简单地说，每个节点的更新方法都会发生初始异步方法调用，该方法会在一段时间内无限期更新（true）{...}）。他的问题是拥有数千个线程似乎不是一个好主意！

看起来这应该有一个简单的解决方案；这与元胞自动机并没有太大的不同，但是我提出的任何同步解决方案要么必须更新大量的节点数，才能从一端到另一端获取消息，要么解决某种复杂的具有多个起点的图行走问题。

异步方法看起来非常简单，如果我能拥有数千个线程就好了……

那么做这样的事情的最好方法是什么？

4

2 回答 2

1

我认为 Rx ( The Reactive Extensions ) 将是一个很好的起点。

其他节点可能需要依赖的每条状态都以 an 形式公开，IObserable<TState>然后其他节点可以订阅这些 observable：

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

Rx 为 observables 提供了许多过滤和处理功能：这些可用于过滤重复事件（但您当然需要定义“重复”）。

这是一篇介绍性文章：http ://weblogs.asp.net/podwysocki/archive/2009/10/14/introducing-the-reactive-framework-part-i.aspx

于 2012-05-13T09:36:35.993 回答
0

首先，您需要确保您的更新收敛。这与您如何执行它们（同步、异步、串行或并行）无关。

假设您有两个节点 A 和 B，它们是连接。A改变，触发B重新计算。B再改变，触发A重新计算。如果A的重新计算改变了A的值，就会触发B的重新计算，以此类推。您需要这一系列触发器在某一点停止 - 您需要收敛您的更改。如果他们不这样做，那么您使用的任何技术都无法修复它。

一旦你确定计算收敛并且你不会陷入无休止的重新计算，你应该从简单的单线程同步计算开始，看看它是否表现良好。如果速度够快，就停在那里。如果没有，您可以尝试并行化它。

我不会为每个计算创建一个线程，它根本无法扩展。而是使用需要执行的计算队列，并且每次更改节点 A 的值时，将其所有邻居都放入队列中。您可以让几个线程处理队列，使其成为更具可扩展性的架构。

如果这还不够快，您需要优化放入队列的内容以及处理方式。我认为现在担心这个还为时过早。

于 2012-05-13T10:24:46.807 回答