Оптимизация производительности вложенных циклов - PullRequest
Новая
       5

Оптимизация производительности вложенных циклов

0 голосов
/ 07 октября 2018

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

std::array<int,3> max = { 3, 4, 6};
for(int i = 0; i <= max.at(0); ++i){
    for(int j = 0; j <= max.at(1); ++j){
       for(int k = 0; k <= max.at(2); ++k){  
           DoSomething(i, j, k);
       }
     }
 }

Очевидно, что мне действительно нужно больше вложенных элементов, а правило "max" более сложное, но идея ясна, я думаю.Я реализовал эту идею, используя рекурсивный подход: 

std::array<int,3> max = { 3, 4, 6};
std::array<int,3> index = {0, 0, 0};
int total_depth = 3;
recursive_nested_for(0, index, max, total_depth);

, где 

void recursive_nested_for(int depth, std::array<int,3>& index,
                     std::array<int,3>& max, int total_depth)
{
    if(depth != total_depth){
        for(int i = 0; i <= max.at(depth); ++i){
            index.at(depth) = i;
            recursive_nested_for(depth+1, index, max, total_depth);
        }
    }
    else
        DoSomething(index);  
}

Чтобы максимально сохранить, я объявляю все переменные, которые я использую, глобальными в реальном коде.

Поскольку эта часть кода занимает очень много времени, можно ли что-нибудь сделать, чтобы ускорить ее?Я также был бы открыт, чтобы написать 24 вложенных для, если необходимо, по крайней мере, избежать накладных расходов!Я подумал, что, возможно, такой подход, как шаблоны выражений для генерации во время компиляции, для которого они вложены, может быть более элегантным.Но возможно ли это?Любое предложение будет с благодарностью.Спасибо всем.

1 Ответ

0 голосов
/ 07 октября 2018

recursive_nested_for() хорошая идея.Это немного негибко, поскольку это в настоящее время написано.Однако вы можете использовать std::vector<int> для измерений и индексов массива или сделать его шаблоном для обработки любого размера std::array<>.Компилятор может встроить все рекурсивные вызовы, если он знает, насколько глубока рекурсия, и тогда он, вероятно, будет столь же эффективен, как и три вложенных цикла for.

Другой вариант - использовать один дляцикл для приращения индексов, которые необходимо увеличить: 

void nested_for(std::array<int,3>& index, std::array<int,3>& max)
{
    while (index.at(2) < max.at(2)) {
      DoSomething(index);

      // Increment indices
      for (int i = 0; i < 3; ++i) {
          if (++index.at(i) >= max.at(i))
             index.at(i) = 0;
          else
             break;
      }
   }
}

Однако вы также можете рассмотреть возможность создания линейной последовательности, которая посещает все возможные комбинации итераторов i, j, k и т. д.,Например, с размерами массива {3, 4, 6} существует 3 * 4 * 6 = 72 возможных комбинаций.Таким образом, у вас может быть один счетчик от 0 до 72, а затем «разбить» этот счетчик на три значения итератора, которые вам нужны, например, так: 

for (int c = 0; c < 72; c++) {
    int k = c % 6;
    int j = (c / 6) % 4;
    int i = c / 6 / 4;
    DoSomething(i, j, k);
}

Вы можете обобщить это на столько измерений, сколько вам нужнохочу.Конечно, чем больше у вас измерений, тем выше стоимость разбиения линейного итератора.Но если размеры вашего массива равны двум, это может быть очень дешево.Кроме того, может случиться так, что вам вообще не нужно разбивать его;например, если вы вычисляете сумму всех элементов многомерного массива, вам не нужны фактические индексы i, j, k и т. д., вы просто хотите посетить все элементы один раз.Если массив расположен в памяти линейно, то вам просто необходим линейный итератор.

Конечно, если у вас есть 24 вложенных цикла, вы заметите, что произведение всех размеров измерения станеточень большое количествоЕсли он не помещается в 32-разрядное целое число, ваш код будет очень медленным.Если оно больше не вписывается в 64-битное целое число, оно никогда не завершится.

...