Modify items in List<T> fast

本文关键字：gt fast items lt List Modify in | 更新日期: 2023-09-27 17:53:51

我尝试使用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;
        }
    }
}

Modify items in List<T> fast

由于数据访问模式的原因，该代码在并行情况下执行得更差。

加快速度的最好方法是认识到你不需要考虑所有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 */ }
}

不仅复杂度更好，缓存行为也更优越。并且它可以在多个线程之间进行拆分，从而大大减少缓存争用。

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

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

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

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

相关文章：