c# – 并行化传递减少

概述我有一个字典< int,List< int>>,其中Key表示集合的元素(或面向图中的顶点),List是一组与Key相关的其他元素(所以从键到值有定向边.字典已针对创建Hasse图进行了优化,因此值始终小于Key. 我还有一个简单的顺序算法,删除所有传递边缘(例如,我有关系1-> 2,2-> 3和1-> 3.我可以删除边缘1-> 3,因为我有1到3之间的路径2). for(int i = 1; i 我有一个字典< int,List< int>>,其中Key表示集合的元素(或面向图中的顶点),List是一组与Key相关的其他元素(所以从键到值有定向边.字典已针对创建Hasse图进行了优化,因此值始终小于Key.

我还有一个简单的顺序算法,删除所有传递边缘(例如,我有关系1-> 2,2-> 3和1-> 3.我可以删除边缘1-> 3,因为我有1到3之间的路径2).

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),结果速度不会显着增加(锁定可能存在问题).我可以并行化外循环吗？

解决方法 有简单的方法来解决并行化问题,分离数据.从原始数据结构读取并写入新的.这样你就可以并行运行它而不需要锁定.

但可能并行化并不是必需的,数据结构效率不高.你使用字典,其中数组就足够了(因为我理解代码你有顶点0..result.Count-1).并列出< int>用于查找. List.Contains是非常低效的. HashSet会更好.或者,对于更密集的图形,BitArray.因此,而不是Dictionary< int,List< int>>您可以使用BitArray [].

我重写了算法并进行了一些优化.它不会生成图形的简单副本并删除边缘,它只是从右边缘构造新图形.它使用BitArray []作为输入图形,使用List< int> []作为最终图形,因为后者更稀疏.

int sizeOfGraph = 1000;//create vertices of a graphBitArray[] inputGraph = new BitArray[sizeOfGraph];for (int i = 0; i < inputGraph.Length; ++i){    inputGraph[i] = new BitArray(i);}//fill random edgesRandom 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 closurefor (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 reductionList<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.");

编辑

我写了这个：
代码有一些问题.随着我现在的方向,您可以删除您需要的边缘,结果将是不正确的.结果证明这是一个错误.我这样想,让我们有一个图表

1->02->1,2->03->2,3->1,3->0

顶点2被顶点1缩小,所以我们有

1->02->13->2,3->0

现在顶点3被顶点2缩小

1->02->13->2,3->0

并且我们有一个问题,因为我们不能减少因为2-> 0减少而留在这里的3> 0.但这是我的错,这绝不会发生.内循环严格地从低到高,所以相反

顶点3被顶点1缩小

1->02->13->2,3->1

现在由顶点2

1->02->13->2

结果是正确的.我为错误道歉.

@H_@R_301_6939@_70@ 总结

以上是内存溢出为你收集整理的c# – 并行化传递减少全部内容，希望文章能够帮你解决c# – 并行化传递减少所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。