1

更新：

这个讨论比我预期的更深入，所以当这个问题突然出现在我脑海中时，我正在使用我实际正在处理的代码来更新它。在我的 C++ 入门课程中，决定谁是井字游戏的赢家需要 8 到 16 行代码。

注意：这旨在与课程保持一致，

注 2： token 是 x 或 o 或 ' ' 的字符

这是一个优化问题。如果这是重复，我很抱歉，但我无法在其他地方找到答案。

基本上，它归结为以下代码是否会更好地循环：

    char CheckForWinner() {

    //returns the token of the player that satisfies one of the winning requirements
    if (Square[0][0] == Square[0][1] && Square[0][0] == Square[0][2] ) { //If all three tokens in the first row are the same
        return Square[0][0]; //Return the token
    } else if (Square[1][0] == Square[1][1] && Square[1][0] == Square[1][2] ) { //Check the next row
        return Square[1][0]; //Return the token
    } else if (Square[2][0] == Square[2][1] && Square[2][0] == Square[2][2] ) {
        return Square[2][0];
    } else if (Square[0][0] == Square[1][0] && Square[0][0] == Square[2][0] ) { //If no rows satisfy conditions, check columns
        return Square[0][0]; //Return the token
    } else if (Square[0][1] == Square[1][1] && Square[0][1] == Square[2][1] ) { 
        return Square[0][1];
    } else if (Square[0][2] == Square[1][2] && Square[0][2] == Square[2][2] ) { 
        return Square[0][2];
    } else if (Square[0][0] == Square[1][1] && Square[0][0] == Square[2][2] ) { //finally, check diagonals
        return Square[0][0];
    } else if (Square[0][2] == Square[1][1] && Square[0][2] == Square[2][0] ) {
        return Square[0][2];
    }

    return ' ';
}

这对他们只需键入 100 行 cout 行的系统是否或多或少会造成负担？

我很好奇，因为看起来我们不仅执行了 100 行计算，而且还为内存分配了一个新变量，并强制计算机处理 100 个数学方程并输出数据。

我可以理解编译器可能会提供某种程度的优化，但我有兴趣在更一般的层面上了解。首先，我使用 VisualStudio 2012 或 MingGW (g++) 进行编译。

4

4 回答 4

5

关于展开循环的所有 100 次迭代是否有效，没有单一的答案。

对于没有代码缓存的“较小”系统，展开所有 100 次迭代的机会非常好，至少在执行速度方面是最佳的。另一方面，一个足够小以至于它的 CPU 没有缓存的系统通常会在其他资源上受到足够的限制，这样做是非常不可取的。

如果系统确实有缓存，那么展开循环的所有 100 次迭代很可能会导致执行速度变慢。几乎可以肯定，循环本身的开销比重新获取基本相同的代码 100 次花费的时间更少。

在典型情况下，当循环的几次迭代被展开（但通常少于 100 次迭代）时，循环展开最有效。在典型情况下，您会看到展开大约 4 到 16 次迭代的广阔平台。

然而，正如许多第一次尝试优化的典型情况一样，我猜你真的在寻找完全错误的方向。如果您想优化该循环，那么（到目前为止）最大的收益可能来自对您在循环中所做的事情进行轻微更改。我敢打赌，你从展开循环中获得的任何改进都太小而无法可靠地衡量，更不用说实际注意到了（即使你将迭代次数从 100 增加到例如几百万）。

另一方面，如果您重写循环以消除每次迭代不必要的缓冲区刷新：

for ( int i = 1; i <= 100; i++ ) 
    cout << i << "\n";

[如果您没有意识到：std::endl在流中插入换行符并刷新流。在大多数情况下（可能包括这种情况），缓冲区刷新是不必要的，可能是不可取的。删除它可以大大提高速度——以 8:1 或 10:1 的系数提高速度是相当普遍的。]

很可能根本不需要太多时间来测量速度的差异。您很有可能能够在 100 次迭代中对其进行测量，如果您尝试更多次迭代，差异可能会变得非常明显。

当您处理一个不受 I/O 限制的循环时，并且不会像这样进行明显的大规模改进时，循环展开可能会成为一种更有吸引力的选择。在这种情况下，您首先需要知道大多数编译器可以自动展开循环，因此尝试在源代码中执行此操作不太可能有很大帮助，除非这为其他优化提供了机会（例如，如果您有一个循环确实在偶数迭代上做一件事，在奇数迭代上做另一件事，展开这两个迭代可以完全消除条件和跳转等，因此手动执行可能会提供有意义的改进，因为编译器可能不会“注意到”奇数/均匀模式并消除条件，跳跃等。

另请注意，现代 CPU 可以（并且通常会）并行执行代码，并推测性地执行代码，这可以消除循环的大部分开销。由于循环的分支几乎总是会被采用（即，除了最后一次迭代之外），CPU 的分支预测器会预测它是被采用的，因此 CPU 可能会同时“进行”多次迭代的指令，即使当你不要展开循环。循环本身的大部分代码（例如，递增i）可以与循环中的至少一些其他代码并行执行，因此循环的开销无论如何都可能非常小。

编辑2：看看手头的具体问题，我想我会以不同的方式完成这项工作。我没有将 TTT 板存储为 2D 数组，而是将其存储为一对位图，一个用于 X，另一个用于 O。这使您可以在单个操作中测试整个获胜组合，而不是三个单独的比较。由于每一行是 3 位，因此使用八进制作为常量可能是最简单的：

static const std::array<short, 8> winners = {
    /* rows */      0007, 0070, 0700, 
    /* columns */   0111, 0222, 0444, 
    /* diagonals */ 0124, 0421
};

在这种情况下，我几乎肯定会使用循环：

char CheckForWinner(short X, short O) { 
    // `winners` definition from above goes here.

    for (int i=0; i<winners.size(); i++) {
        if (X & winners[i] == winners[i])
            return 'X';
        if (O & winners[i] == winners[i])
            return 'O';
    }
    return ' ';
}

这里最大的问题是您是否真的想分别通过 X 和 O 板，或者通过一组两条短裤是否更有意义。使用阵列的明显优势是更容易访问对面的板。例如，要测试是否允许在一个板上移动，您将检查该位是否在另一个板上设置。将棋盘存储在数组中，您可以传递一个n指示要移动的棋盘，并使用它1-n来获取另一个棋盘，在那里您将检查该位是否已设置。

于 2013-12-02T05:14:34.610 回答
4

您所说的称为循环展开。性能权衡很复杂，取决于编译器和执行环境的许多方面。有关这些问题的讨论，请参阅有关循环展开的 Wikipedia 文章。

于 2013-12-02T05:11:05.987 回答
3

通过编码哪些位置是哪些行的一部分，您可以非常有效地执行获胜检查：

char square[3][3] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '};
char player = 'x';
unsigned progress[2];

const unsigned lines[3][3] = {
    0x10010010,
    0x10001000,
    0x10000101,

    0x01010000,
    0x01001011,
    0x01000100,

    0x00110001,
    0x00101000,
    0x00100110
};

编码为“顶行、中间行、底行、左列、中列、右列、向下对角线、向上对角线”。

例如，左上角位置是顶行、左列和向下对角线的一部分。

一旦您在同一行中有 3 个棋子，则该行已满并且您获胜，因此只需继续添加行直到您达到 3。您可以通过两个连续的 1 位识别 3，因此p & (p >> 1)将是非零：

void make_move(int y, int x)
{
    square[y][x] = player;
    unsigned p = (progress[player & 1] += lines[y][x]);
    if (p & (p >> 1))
    {
        printf("player %c has won!\n", player);
        exit(0);
    }
    else
    {
        player = 'x' + 'o' - player;
    }
}
于 2013-12-02T19:06:47.023 回答
2

在考虑循环展开时，有必要估计循环体与循环组织开销之间的权重比。

确实，即使是最简单的 for 循环也会增加几条指令开销。但在您的情况下，I/O 调用的复杂性会使这些指令超重 10-100 倍。

当循环体在内存中进行一些操作时，展开是有意义的，这需要几个，也许是十几个 asm 指令。例如：

// Process digits starting fom the last one.
wchar_t carry_bit = 0;
while (curr_digit_offs >= 0)
{
    wchar_t ch = fpb[curr_digit_offs];
    fpb[curr_digit_offs--] = g_RawScan_MultiplyBy2[ch & 15] + carry_bit;
    carry_bit = (ch >= L'5') ? TRUE : FALSE;
}

在上面的例子中，循环体没有调用任何外部函数。它仅适用于内存中的数据结构。这意味着可以估计其复杂性。

在每种特定情况下，都需要单独估计。

于 2013-12-02T05:18:20.457 回答