оптимизация кода C со встроенными циклами for

Question

    void evolve(board prv, board nxt){
      
       int i, j;
       int n;
    
       printf("\rGeneration %d\n", generation++);
       if (printLazy == 1){
         lazyPrint(prv);
       
for (j=0; j < WIDTH; ++j) {
          for (i = 0; i < HEIGHT; ++i) {
             n = neighbors(prv, i, j);
             if (prv[i][j] && (n == 3 || n == 2))
                nxt[i][j] = true;
             else if (!prv[i][j] && (n == 3)) 
                nxt[i][j] = true;
             else
                nxt[i][j] = false;
          }
       }
    }

** Некоторые просили меня добавить метод соседей, чтобы

static int neighbors (board b, int i, int j) {
   int n = 0;
   int i_left = max(0,i-1);
   int i_right  = min(HEIGHT, i+2);
   int j_left = max(0,j-1);
   int j_right  = min(WIDTH, j+2);
   int ii, jj;

   for (ii = i_left; ii < i_right; ++ii) {
      for (jj = j_left; jj < j_right; ++jj) {
         n += b[ii][jj];
      }
   }

   return n - b[i][j];
}

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

void evolve(board prv, board nxt) {
  
   register int i, j;
   int n;
   bool next;

   printf("\rGeneration %d\n", generation++);
   if (printLazy == 1){
     lazyPrint(prv);
   }
   
   for (j=0; j < WIDTH; ++j) {
      for (i = 0; i < HEIGHT; ++i) {
         n = neighbors(prv, i, j);
         if (prv[i][j])
                if (n == 2)
                        next = true;
                else if (n == 3)
                        next = true;
                else
                        next = false;
         else
                if(n == 3)
                        next = true;
                else
                        next = false;
         nxt[i][j] = next;
      }
   }
}

Есть ли лучший способ сделать это или есть ли какие-либо ресурсы или видео, которые вы все порекомендуете?

Спасибо, любая помощь приветствуется.

Answer 1

Некоторые идеи Встроить вашу функцию neighbors(). Или превратить его в макрос. Уберите условное. Чтобы развернуть внутренний l oop, замените каждое использование i буквальными значениями, чтобы ваш код выглядел так:

for (j =0;.......
   n = fun(prev, 0 ,j);
   If.....
      n = fun(prev, 1, j);
   if......

и так далее. Если значение HEIGHT было, скажем, 100, то вы получите взрыв кода из 100 вызовов функций и 100 составных условий. Еще хуже, если развернуть внешний л oop.

Answer 2

Если n был ограничен, чтобы сказать 8 соседей, используйте таблицу поиска

bool foo[2][8] = { [1][2] = true,  [1][3] = true, [0][3] = true };

for (j=0; j < WIDTH; ++j) {
  for (i = 0; i < HEIGHT; ++i) {
    n = neighbors(prv, i, j);
    nxt[i][j] = foo[prv[i][j]][n];
  }
}

Общая слабость - это сама функция neighbors(prv, i, j). Один трюк, чтобы увеличить размер 2D-массива на 1 со всех четырех сторон и заполнить край false, чтобы neighbors() всегда мог проверить 8 соседей, поскольку он никогда не используется на краю / углах.

Убедитесь, что 2-е измерение в степени 2 также помогает - упрощает расчет индекса. Итак, если исходный массив 12*11, создайте новый массив (1+12+1)*(1+11+1+4) или 14*16.

Answer 3

Начнем с n, если n == 3 nxt[i][j] = true;. Итак, моя первая оптимизация будет:

if (n == 3)
    nxt[i][j] = true;
else if (n == 2 && prv[i][j])
    nxt[i][j] = true;
else
    nxt[i][j] = false;

, поэтому из 8 сравнений вы снизитесь до 3. Или, что еще лучше,

if (n == 3 || (n == 2 && prev[i][j]))
    nxt[i][[j] = true;
else
    nxt[i][j] = false;

во втором примере меньше прыжков. Есть еще один трюк, который может быть выполнен компилятором:

if (n == 3 || (!(n & 1) && !prev[i][j]))
    nxt[i][[j] = true;
else
    nxt[i][j] = false;

РЕДАКТИРОВАТЬ: Я ошибся в ошибке, но также хочу уточнить свой ответ.

if (prv[i][j] && (n == 3 || n == 2))

становится

if (prev[i][j] && n==3 || prev[i][j] && n == 2)

так что у вас есть

if (prev[i][j] && n==3 || prev[i][j] && n == 2)
else if (!prev[i][j] && n == 3)
else ...

так что если n == 3 nxt[i][[j] = true; всегда !!!! Осталось n == 2 && prev[i][j] для второго оператора.