改进局部性时嵌套 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++;
        }
    }
}

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

Ranges of nested for-loops when locality is improved (C++)

c++

nested-loops

cache-locality