c# - 快速修改 List 中的项目

Question

我尝试使用 Parallel.ForEach 和 ConcurrentBag 使这段代码执行得更快，但它仍然运行很长时间(尤其是考虑到在我的场景中我也可能是 1.000.000++):

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;
        }
    }
}

Answer 1

由于数据访问模式，该代码将并行执行 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 */ }
}

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