Оптимизируйте базовую c вложенную l oop in C, написав цикл - PullRequest
Новая
       13

Оптимизируйте базовую c вложенную l oop in C, написав цикл

0 голосов
/ 01 марта 2020

Текущий l oop: 

#define N 3000
...
int i, j;
int a[N][N], b[N][N], c[N]; 
// Fill in b and c with random values

for (i = 0; i < n; ++i) {
  for (j = 0; j < n; ++j) {
    a[i][j] = b[i][j] / c[i];
  }
}

Моя оптимизированная версия развертывает как внешнюю, так и внутреннюю l oop: 

for (int i = 0; i < N; i += 2) {
    for (int j = 0; j < N; j += 2) {
      a[i][j] = b[i][j] / c[i];
      a[i][j + 1] = b[i][j + 1] / c[i];
      a[i + 1][j] = b[i + 1][j] / c[i + 1];
      a[i + 1][j + 1] = b[i + 1][j + 1] / c[i + 1];
    }
  }

Однако мой инструктор сказал, что второй l oop не очень хорошо оптимизирован. Указание на c (i) должно быть взято из l oop над j. L oop оптимизируется путем изменения порядка индексов. Таким образом, вы совершаете один проход по внутренней памяти l oop вместо зигзагообразных поисков.

Я до сих пор не уверен, что он имеет в виду, так как изменение порядка индексов все равно сделает l oop траверс по зигзагообразному типу. Каким должно быть правильное решение для этого случая?

Ответы [ 2 ]

2 голосов
/ 02 марта 2020

Я не уверен, что ищет ваш инструктор, но вы можете использовать достаточно известную технику C, известную как Устройство Даффа , чтобы ускорить процесс. вверх по развернутому l oop: 

  init_arrays();

  precomputed_n = (N + 7) / 8;

  for(i = 0 ; i < N ; ++i)
    {
    to = a[i];
    from = b[i];
    ci = c[i];

    n = precomputed_n;

    switch(N % 8)
      case 0: do { *to++ = *from++ / ci;
      case 7:      *to++ = *from++ / ci;
      case 6:      *to++ = *from++ / ci;
      case 5:      *to++ = *from++ / ci;
      case 4:      *to++ = *from++ / ci;
      case 3:      *to++ = *from++ / ci;
      case 2:      *to++ = *from++ / ci;
      case 1:      *to++ = *from++ / ci;
                 } while (--n > 0);
    }

Устройство Даффа - это удобный способ развернуть петли, который сочетает в себе while l oop и switch.

Попробуйте онлайн!

2 голосов
/ 02 марта 2020

Поместите int ci = c[i]; во внешний l oop, а внутренний l oop делится на ci. Обратите внимание, что любой разумный компилятор сделает это за вас.

...