异步更新图形？

我在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）{...}）中无限期地更新。他的问题是拥有数千个线程似乎不是一个好主意！

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

异步方法似乎平凡简单，只要我能有数千个线程...

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

来源

2012-05-13 JMP

那么这是否意味着每个节点变化影响（间接）所有其他节点？ –

是的，它的确如此。可以想象，一个节点可以选择在暴露状态下传递状态，但不保持它的外部状态，以允许消息“传递”给知道监听它们的节点。 – JMP

我认为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-13 09:36:35 Richard

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

假设你有两个节点A和B，是连接。 A转换，引发B. B的重新计算，然后改变，触发A.如果A的重新计算改变的价值进行重新计算，将触发B的重新计算等。你需要这一系列的触发器来停止一个点 - 你需要你的改变来收敛。如果他们不这样做，没有任何技术可以解决它。

一旦确定计算收敛，你不进入无休止的重新计算，你应该用简单的单线程计算同步启动，看看它是否表现良好。如果速度够快，就到那里吧。如果没有，你可以尝试并行化。

我不会创建每次计算线程，它不适合所有。而是使用了需要执行的计算的队列，每次更改节点A的价值，把它的所有邻国在队列中。您可以有几个线程处理队列，使其成为一个更具可扩展性的体系结构。

如果这个仍然速度不够快，您需要优化您放入队列中的内容以及如何处理它。我认为现在担心这一点还为时过早。

来源

2012-05-13 10:24:46 zmbq

异步更新图形？

回答

相关问题