異步更新圖形？

我在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

異步更新圖形？

回答

相關問題