局部性得到改进时嵌套的 for 循环的范围 (C++)

Question

我有以下嵌套的循环：

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）。

我理解它为什么要这样做，但我一生都想不出解决方案;任何帮助将不胜感激。

Answer 1

首先，您需要确保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++;
        }
    }
}