Быстрое изменение элементов в списке

#c#

Вопрос:

Я попытался ускорить выполнение этого кода, используя 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 amp;amp; (point.X - innerPoint.X) < 2) {
            innerPoint.Y = point.Y;
            point.CanDelete = true;
        }
    }
}

1. Опишите, чего вы пытаетесь достичь. O (N ^ 2) — это слишком даже для N >= 20000 .

2. Если вы действительно собираетесь иметь в своей коллекции более миллиона элементов, возможно, вам захочется начать поиск алгоритмов получше, чем вложенный цикл… независимо от того, распределите ли вы это на несколько ядер с распараллеливанием или нет, все равно потребуется 10 ^ 12 итераций, что немало (и вы понимаете, что это приведет к удалению, например, линии точек, какой бы длинной она ни была, при условии, что точки находятся достаточно близко друг к другу, верно?)

3. Мне нужно получить все точки в точках с максимальным Y для каждого X , тогда как X может отличаться от x1-x2 <допуск. мои значения — это просто демонстрационные данные. реальные значения отличаются, но размеры списка похожи.

4. @Alexander: Я не вижу ничего max Y в вашей существующей логике.

5. @matti-virkkunen, как ты думаешь, есть ли точки. Где (p=> point.X-p.X<2) выполняется быстрее?

Ответ №1:

Этот код будет хуже выполняться параллельно из-за шаблонов доступа к данным.

Лучший способ ускорить это — признать, что вам не нужно рассматривать все 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 amp;amp; points[k].X > x1 - 2; --k ) { /* merge points */ }
  for (int k = j   1; k < points.Length amp;amp; points[k].X < x1   2;   k ) { /* merge points */ }
}

Улучшилась не только сложность, но и поведение кэша намного лучше. И это может быть разделено между несколькими потоками с гораздо меньшим конфликтом в кэше.

Ответ №2:

Что ж, я не знаю точно, чего вы хотите, но давайте попробуем.

Во-первых, при создании списка вы можете задать его желаемый начальный размер, поскольку вы знаете, сколько элементов он будет содержать. Таким образом, ему не нужно постоянно расти.

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

Затем вы могли бы отсортировать список по свойству X. Таким образом, вы бы сравнивали каждую точку только с ближайшими к ней точками: когда вы обнаружите, что первая, прямая или обратная, находится слишком далеко, вы можете прекратить сравнение.