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

Question

我有以下嵌套的for循环：

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用于索引两个一维数组）并采用了我相信是一种相当标准的技术：

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++;
        }
    }
}