並行化傳遞減少

Question

我有一個Dictionary<int, List<int>>，其中Key表示一個集合（或一個方向圖中的一個頂點）的一個元素，而List是一組與Key有關的其他元素（所以面向從鍵到值的邊緣）。該字典爲創建Hasse圖而進行了優化，因此值始終小於密鑰。我也有一個簡單的順序算法，刪除所有傳遞邊（例如我有關係1-> 2，2-> 3和1-> 3。我可以刪除邊1-> 3，因爲我有經由2）在1和3之間的路徑）。

for(int i = 1; i < dictionary.Count; i++) 
{ 
    for(int j = 0; j < i; j++) 
    { 
     if(dictionary[i].Contains(j)) 
       dictionary[i].RemoveAll(r => dictionary[j].Contains(r)); 
    } 
} 

是否可以並行化算法？我可以爲內部循環執行Parallel.For。但是，建議不要這樣做（https://msdn.microsoft.com/en-us/library/dd997392(v=vs.110).aspx#Anchor_2），所產生的速度不會顯着增加（+可能存在鎖定問題）。我可以並行化外部循環嗎？

Answer 1

有簡單的方法來解決並行化問題，分離數據。從原始數據結構中讀取並寫入新的。這樣你就可以並行運行而不需要鎖定。

但可能並行化甚至沒有必要，數據結構並不高效。你使用字典的地方陣列就足夠了（因爲我知道代碼你有頂點0..result.Count-1）。和List<int>查找。 List.Contains效率很低。 HashSet會更好。或者，對於更密集的圖，BitArray。所以，而不是Dictionary<int, List<int>>您可以使用BitArray[]。

我重寫了算法並做了一些優化。它不會製作圖形的簡單副本並刪除邊緣，只會從右邊緣構建新圖形。它使用BitArray[]作爲輸入圖，List<int>[]用於最終圖，因爲後者更稀疏。

int sizeOfGraph = 1000; 

//create vertices of a graph 
BitArray[] inputGraph = new BitArray[sizeOfGraph]; 
for (int i = 0; i < inputGraph.Length; ++i) 
{ 
    inputGraph[i] = new BitArray(i); 
} 

//fill random edges 
Random rand = new Random(10); 
for (int i = 1; i < inputGraph.Length; ++i) 
{ 
    BitArray vertex_i = inputGraph[i]; 
    for(int j = 0; j < vertex_i.Count; ++j) 
    { 
     if(rand.Next(0, 100) < 50) //50% fill ratio 
     { 
      vertex_i[j] = true; 
     } 
    } 
} 

//create transitive closure 
for (int i = 0; i < sizeOfGraph; ++i) 
{ 
    BitArray vertex_i = inputGraph[i]; 
    for (int j = 0; j < i; ++j) 
    { 
     if (vertex_i[j]) { continue; } 
     for (int r = j + 1; r < i; ++r) 
     { 
      if (vertex_i[r] && inputGraph[r][j]) 
      { 
       vertex_i[j] = true; 
       break; 
      } 
     } 
    } 
} 

//create transitive reduction 
List<int>[] reducedGraph = new List<int>[sizeOfGraph]; 
Parallel.ForEach(inputGraph, (vertex_i, state, ii) => 
{ 
    { 
     int i = (int)ii; 
     List<int> reducedVertex = reducedGraph[i] = new List<int>(); 

     for (int j = i - 1; j >= 0; --j) 
     { 
      if (vertex_i[j]) 
      { 
       bool ok = true; 
       for (int x = 0; x < reducedVertex.Count; ++x) 
       { 
        if (inputGraph[reducedVertex[x]][j]) 
        { 
         ok = false; 
         break; 
        } 
       } 
       if (ok) 
       { 
        reducedVertex.Add(j); 
       } 
      } 
     } 
    } 
}); 

MessageBox.Show("Finished, reduced graph has " 
    + reducedGraph.Sum(s => s.Count()) + " edges."); 

編輯

我寫了這個： 的代碼有一些問題。隨着方向i現在，您可以刪除您需要的邊緣，結果將是不正確的。原來這是一個錯誤。我是這樣想的，讓有圖

1->0 
2->1, 2->0 
3->2, 3->1, 3->0 

頂點2得到由頂點1減少，所以我們必須

1->0 
2->1 
3->2, 3->1, 3->0 

現在頂點3被通過頂點2

1->0 
2->1 
3->2, 3->0 

減少我們有一個問題，因爲我們不能減少3->0因爲減少2->0在這裏留下。但這是我的錯誤，這絕不會發生。內循環進入嚴格從低到高，所以不是

頂點3得到由頂點1

1->0 
2->1 
3->2, 3->1 

降低，現在由頂點2

1->0 
2->1 
3->2 

而結果是正確的。我爲錯誤表示歉意。