Диапазоны вложенных циклов for при улучшении локальности (C ++)

У меня есть следующие вложенные для цикла:

int n = 8;
int counter = 0;

for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
printf("(%d, %d)\n", i, j);
counter++;
}
}

Который печатает (0,1) — (6,7), как ожидается, и printf() Заявление выполняется 28 раз, как указано counter,

Передо мной была поставлена ​​задача повысить эффективность этого кода путем улучшения его локальности (это тестовый код, значение n в реальной программе гораздо больше и i а также j используются для индексации в два 1d-массива) и используют то, что я считаю довольно стандартным методом:

int chunk = 4;

for(int i = 0; i < n; i+=chunk)
for(int j = 0; j < n; j+=chunk)
for (int i_chunk = 0; i_chunk < chunk; i_chunk++)
for (int j_chunk = i_chunk + 1; j_chunk < chunk; j_chunk++)
{
printf("(%d, %d)\n", i+i_chunk, j+j_chunk);
counter++;
}

Однако здесь printf() запускается только 24 раза, потому что j_chunk = i_chunk + 1 означает, что где до j цикл напечатан (0,1) — (0,7), две итерации j_chunk цикл где i+i_chunk == 0 печать (0,1) — (0,3) и (0,5) — (0,7) отсутствует (0,4).

Я понимаю, почему он это делает, но я не могу ради жизни придумать решение; любая помощь будет оценена.

0

Решение

Для начала нужно убедиться, что j никогда не в более низком, чем iпоэтому ваши внешние петли должны быть:

for(int i = 0; i < n; i+=chunk)
for(int j = i; j < n; j+=chunk)

Тогда вам нужно другое поведение в зависимости от того, i а также j находятся в одном куске или нет. Если они, j_chunk должен всегда быть больше, чем i_chunkВ противном случае вам необходимо пройти все возможные комбинации:

if(i==j)
{
for (int i_chunk = 0; i_chunk < chunk; i_chunk++)
{
for (int j_chunk = i_chunk + 1; j_chunk < chunk; j_chunk++)
{
printf("(%d, %d)\n", i+i_chunk, j+j_chunk);
counter++;
}
}
}
else
{
for (int i_chunk = 0; i_chunk < chunk; i_chunk++)
{
for (int j_chunk = 0; j_chunk < chunk; j_chunk++)
{
printf("(%d, %d)\n", i+i_chunk, j+j_chunk);
counter++;
}
}
}
0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector