Алгоритм оптимизации вложенных циклов

Question

Существует ли алгоритм для оптимизации производительности следующего?

for (i = 0; i < LIMIT; i++) {
  for (j = 0; j < LIMIT; j++) {
   // do something with i and j
  }
 }

• Оба i и j начинаются с 0
• Оба цикла заканчиваются наодно и то же условие
• И i, и j увеличиваются с одинаковой скоростью

Можно ли это как-то сделать в 1 цикле?

Answer 1

Это возможно написать это, используя один цикл, но я настоятельно рекомендую не делать этого.Двойной цикл for - это хорошо зарекомендовавший себя термин, который программисты умеют читать, и если вы объединяете два цикла в один, вы жертвуете удобочитаемостью.Более того, неясно, будет ли это на самом деле ускорять выполнение кода, поскольку компилятор уже очень хорошо оптимизирует циклы.Объединение двух циклов в один требует дополнительной математики на каждом шаге, которая почти наверняка медленнее, чем два цикла независимо.

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

(0, 0)   (0, 1),   (0, 2), ...,   (0, N-1)
(1, 0)   (1, 1),   (1, 2), ...,   (1, N-1)
                ...          
(N-1, 0) (N-1, 1), (N-1, 2), ..., (N-1, N-1)

Идея состоит в том, чтобы попытаться посетить все эти пары в порядке (0, 0), (0, 1), ..., (0, N-1), (1, 0), (1, 1), ..., (1, N-1), ..., (N-1, 0), (N-1, 1), ..., (N-1, N-1).Чтобы сделать это, обратите внимание, что каждый раз, когда мы увеличиваем i, мы пропускаем N элементов, тогда как когда мы увеличиваем j, мы пропускаем только один элемент.Следовательно, итерация (i, j) цикла будет отображаться в положение i * N + j в линеаризованном порядке цикла.Это означает, что на итерации i * N + j мы хотим посетить (i, j).Для этого мы можем восстановить i и j из индекса, используя простую арифметику.Если k является текущим счетчиком цикла, мы хотим посетить

i = k / N   (integer division)
j = k % N

Таким образом, цикл может быть записан как

for (int k = 0; k < N * N; ++k) {
    int i = k / N;
    int j = k % N;
}

Однако вы должны быть осторожны с этим, потому что N * N может не вписаться в целое число и, следовательно, может переполниться.В этом случае вы захотите использовать двойной цикл for.Более того, введение дополнительных делений и модулей сделает этот код (потенциально) намного медленнее, чем двойной цикл for.Наконец, этот код гораздо сложнее для чтения, чем исходный код, и вам нужно быть уверенным, что вы предоставите агрессивные комментарии, описывающие, что вы здесь делаете.Опять же, я настоятельно советую вам не делать этого вообще, если у вас нет веских оснований подозревать, что существует проблема со стандартным двойным циклом for.

(Интересно, что здесь также можно использовать хитростьиспользуется для представления многомерного массива с использованием одномерного массива. Логика идентична - у вас есть двумерная структура, которую вы хотите представить с одномерной структурой.)

Надеюсь, это поможет!

Answer 2

Нет способа значительно оптимизировать сам цикл. Однако, когда вы рассматриваете детали «делайте что-то с i и j», может иметь большое значение, является ли i или j внешним циклом. Например, один заказ может вызвать многократное перемещение в памяти или на диске, в то время как другой заказ приводит к последовательному доступу, или почти так.

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

Answer 3

Если вам нужно ускорить цикл for любой ценой, посмотрите, сможете ли вы найти распараллеливающий или векторизованный компилятор и изменить его так, как вам нужно, чтобы воспользоваться этим, или найти способ использовать некоторую библиотеку строительных блоков. , Смотрите, например http://en.wikipedia.org/wiki/Intel_C%2B%2B_Compiler и http://en.wikipedia.org/wiki/Math_Kernel_Library.

(Или найдите лучший алгоритм - часто, который даст вам что-то вроде следующего:

for (i = 0; i < LIMIT; i++) {
  // Do something clever with i 
  // that does not depend on j
  for (j = 0; j < LIMIT; j++) {
    // do something fast with i and j
    // and the results of the clever stuff
    // outside the loop over j
  }
}

)

Answer 4

Вы не можете улучшить производительность биг-О цикла. Тем не менее, существуют алгоритмически-зависимые методы улучшения постоянного фактора, скрытого big-O, с использованием кеша.

Вот пример улучшенного алгоритма транспонирования матрицы: Программа преобразования матрицы с эффективным кешем?

Однако общей темой здесь является то, что мы фактически вводим больше циклов, а не их меньше.

Answer 5

Я недавно столкнулся с той же проблемой ...

Что вы думаете об этом? Единственный цикл while (в вашем примере это индекс внешнего цикла for):

i = 0; j = 0;
while (i<M) {
  // Do something with i and j
  if (j<N-1) {
    j++;
  } else {
    j=0;
    i++;
  }
}

Answer 6

Это зависит от того, нужны ли вам как i, так и j во внутреннем цикле, например, иногда вы можете сгладить такой цикл, как этот:

for (k = 0; k < LIMIT * LIMIT; ++k)
{
    // do something with k
}

, но для всех, кроме самых простых внутренних циклов, это, вероятно, не имеет ощутимого влияния на производительность.

Какую конкретную проблему вы пытаетесь решить?