修改列表中的项目<T> fast

我试图使用Parallel.ForEach和ConcurrentBag更快地执行代码，但它仍然运行的时间很长（特别是在考虑到在我的场景中我也可能是1.000.000 ++ ）：修改列表中的项目<T> fast

List<Point> points = new List<Point>(); 
for(int i = 0; i<100000;i++) { 
    Point point = new Point {X = i-50000, Y = i+50000, CanDelete = false}; 
    points.Add(point); 
} 

foreach (Point point in points) { 
    foreach (Point innerPoint in points) { 
     if (innerPoint.CanDelete == false && (point.X - innerPoint.X) < 2) { 
      innerPoint.Y = point.Y; 
      point.CanDelete = true; 
     } 
    } 
}

来源

2011-04-30 Alexander Zeitler

描述你想达到什么目的。即使对于N> = 20000，O（N^2）也太多了。 – 2011-04-30 19:31:51

如果你真的要在你的集合中有超过一百万个项目，你可能想要开始寻找比嵌套循环更好的搜索算法......是否将它分散到少数几个并行化的核心，它仍然会是10^12次迭代，这是很多的（你会意识到，这将删除，例如，一个点的线，无论多长时间，只要点是彼此足够接近，对吧？） – 2011-04-30 19:32:22

我需要在每个_X_上使用__ __ __ __ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _点所有点，而_X_可以与x 1-x 2 2011-04-30 19:37:57

由于数据访问模式，该代码将并行执行WORSE。

加速它的最好方法是认识到你不需要考虑所有的O（N^2）对点，但只有那些具有附近X坐标的点。

首先，按X坐标排序列表O（N log N），然后在列表中从每个点向前和向后处理，直到离开邻域。你需要使用索引而不是foreach。

如果您的示例数据，列表已经排序。

由于您的距离测试是对称的，并从考虑中删除匹配点，您可以跳过查看早期点。

for (int j = 0; j < points.Length; ++j) { 
    int x1 = points[j].X; 
    //for (int k = j; k >= 0 && points[k].X > x1 - 2; --k) { /* merge points */ } 
    for (int k = j + 1; k < points.Length && points[k].X < x1 + 2; ++k) { /* merge points */ } 
}

不仅复杂性更好，缓存行为也更加优越。它可以在多个线程之间进行拆分，缓存争用少得多。

来源

2011-04-30 19:36:06

感谢本，这是诀窍！非常快速和正确。感谢所有其他人为我指出了正确的方向。 – 2011-04-30 22:14:48

嗯，我不知道你想要什么，但让我们试试。

首先，创建列表时，您可能需要设置所需的初始大小，因为您知道它将容纳多少个项目。所以它不需要一直增长。

List<Point> points = new List<Point>(100000);

接下来，您可以通过X属性对列表进行排序。所以你只能比较每个点和它附近的点：当你发现第一个点，向前或向后，太远时，你可以停止比较。

来源

2011-04-30 19:38:48 Gabriel

修改列表中的项目<T> fast

回答

相关问题