快速修改List <T>中的项目

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 */ }
}

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