c++ - 为什么在与前缀和矩阵相关的问题中 1 个 for 循环比 2 个 for 循环慢？

Question

我最近在做这个问题，直接取自IOI 2010的第3天任务3，“生活质量”，我遇到了一个奇怪的现象。

我正在设置一个 0-1 矩阵并使用它来计算 1 个循环中的前缀和矩阵：

for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;}
        b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + lower[i][j];
    }
}

我在 4 次测试中获得了 TLE（超出时间限制）（时间限制为 2.0 秒）。分别使用 2 for 循环时：

for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;}
    }
}

for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + lower[i][j];
    }
}

给了我完整的交流电（接受）。

从这里的4张图片中我们可以看到：

• TLE 结果，图 1：https ://i.stack.imgur.com/9o5C2.png

• TLE 结果，图 2：https ://i.stack.imgur.com/TJwX5.png

• AC结果，图1：https ://i.stack.imgur.com/1fo2H.png

• AC结果，图2：https ://i.stack.imgur.com/CSsZ2.png

2 个 for 循环代码通常运行得更快一些（即使在接受的测试用例中），这与我认为单个 for 循环应该更快的逻辑形成鲜明对比。为什么会这样？

完整代码（AC）：https ://pastebin.com/c7at11Ha （请忽略所有废话和类似的东西using namespace std;，因为这是一场竞争性编程比赛）。

• 注：评委服务器lqdoj.edu.vn建立在全球编程竞赛平台dmoj.ca之上。

Answer 1

如果您查看程序集，您会看到差异的来源：

1. 单回路：

{
    if (a[i][j] < x)
    {
        lower[i][j] = 0;
    }
    else
    {
        lower[i][j] = 1;
    }
    b[i][j] = b[i-1][j] 
            + b[i][j-1]
            - b[i-1][j-1]
            + lower[i][j];
}

在这种情况下，存在数据依赖性。对 的赋值b取决于对 的赋值lower。因此，操作在循环中按顺序进行 - 首先分配给lower，然后分配给b。由于依赖关系，编译器无法显着优化此代码。

2. 将分配分成 2 个循环：

分配到lower现在是独立的，编译器可以使用SIMD 指令，从而在第一个循环中提高性能。第二个循环或多或少与原始组件相似。