Оптимизация цикла обработки массива

Question

Я работаю над программированием, и я немного сбит с толку. Задача состоит в подсчете количества пересечений дисков на двухмерном плане. x всегда равен 0, а y является индексом в массиве. Радиус элемента хранится в элементе массива. Производительность хороша с количеством элементов, небольшим количеством элементов, но с большим количеством элементов, таких как 10 000 000, производительность плохая. В настоящее время я использую 2 вложенных цикла for для обработки массивов.

Буду признателен за любую помощь. Я привязан к данным мне структурам данных и не могу их изменить. Вычисление, если диск пересекает другой, так как я имею дело с целыми числами, а центральные точки находятся на одной оси y.

Ниже приведен код:

int number_of_intersections ( int A[], int n ) 
{
 int base = 0;
 int inc = 0;
 int intersect = 0;
 int maxrad = 0;
 int x;

 if (n>1)
 { 
  for (base=0;base<(n-1);base++)
  {
   inc = base+1;
   do
   { 
    if ( inc - base <= (A[base] + A[inc]))  
    {                                    
     intersect ++;
     if (!(intersect^10000000))   
     {
      return -1;
     }
    }
    inc ++;
   } while (inc < n);
  }
 }

 return intersect;
}

Спасибо за ваше время

Answer 1

Ваш код пахнет преждевременной оптимизацией.

Избавьтесь от внешнего оператора if, так как в любом случае он вам не очень поможет (внешний цикл не будет выполнен с n <= 1). </p>

Удалите эту магическую константу (10000000) и хитрость (я полагаю).Его трудно читать, он совсем не гибкий (по крайней мере, должен быть константной переменной), и логика плохо выражена при использовании xor вместо == .

Возможно, поменяйте цикл do-while на более легкий для чтения цикл for.(как предложено @Philip Potter)

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

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

Примечание: Не делайте хитрых приемов оптимизации рано. Они вам не помогут любой хорошо.

Редактировать: чтобы прояснить точку; -)

int number_of_intersections (int A[], int n) 
{
     int intersect = 0;
     const int maxIntersections = 10000000;    

     for (int base = 0; base <  n-1; base++)
     {
        for(int inc = base+1; inc < n; inc++)
        { 
           if (inc - base <= A[base] + A[inc])  
           {                                    
              intersect ++;
              if (intersect == maxIntersections) return -1;
           }
        }
     }

     return intersect;
}

Answer 2

ваш подход O (n ^ 2), так как вы тестируете каждую пару дисков, следовательно, плохая скорость при большом количестве дисков.

Я не могу придумать, как улучшить асимптотически лучшую производительность, но есть одна оптимизация, которую вы можете сделать.

скажем, вы находитесь в элементе p, у которого есть радиус m. очевидно, что каждый диск, расположенный в точке p - m <= y <= p + m, имеет центр, покрытый диском в точке y = m. Поэтому вам нужно выполнять какую-либо работу только с дисками, которые находятся дальше. </p>

Answer 3

Как отмечено в комментариях, это действительно одномерная проблема. Фактически, это проблема пересекающихся интервалов, где интервалы [x, y] соответствуют самой низкой и самой высокой координатам x в диске x = center - radius и y = center + radius.

Подумайте о том, чтобы двигаться вдоль точек x и y слева направо. Вы можете сделать это без сортировки, сохранив два указателя на диски, один для точки x и один для точки y. Используйте структуру данных, чтобы отслеживать диски под текущим указателем. Когда вы видите точку x, распознайте пересечение между диском точки и всеми текущими дисками, а затем сделайте его текущим диском. Когда вы увидите точку y, удалите диск этой точки из текущих дисков.