У меня есть следующие вложенные для цикла:
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).
Я понимаю, почему он это делает, но я не могу ради жизни придумать решение; любая помощь будет оценена.
Для начала нужно убедиться, что 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++;
}
}
}
Других решений пока нет …