优化嵌套循环的算法

Question

是否有算法可以优化以下性能？

for (i = 0; i < LIMIT; i++) {
  for (j = 0; j < LIMIT; j++) {
   // do something with i and j
  }
 }

• i 和j 都从 0 开始
• 两个循环都以相同的条件结束
• i 和j 以相同的速率递增

这能以某种方式在 1 个循环中完成吗？

Answer 1

可以用一个循环来写这个，但我强烈建议不要这样做。双 for 循环是程序员知道如何阅读的公认惯用语，如果将两个循环合并为一个循环，就会牺牲可读性。此外，尚不清楚这是否真的会使代码运行得更快，因为编译器已经非常擅长优化循环。将两个循环合并为一个循环需要在每一步进行一些额外的数学运算，这几乎肯定比两个循环独立运行要慢。

也就是说，如果您确实想将此编写为单个循环，一个想法是考虑迭代空间，即您迭代的一组对。现在，它看起来像这样:

(0, 0)   (0, 1),   (0, 2), ...,   (0, N-1)
(1, 0)   (1, 1),   (1, 2), ...,   (1, N-1)
                ...          
(N-1, 0) (N-1, 1), (N-1, 2), ..., (N-1, N-1)

想法是尝试按顺序访问所有这些对 (0, 0), (0, 1), ..., (0, N-1), (1, 0), (1, 1), ..., (1, N-1), ..., (N-1, 0), (N-1, 1), ..., (N-1, N-1 )。为此，请注意每次我们增加 i 时，我们都会跳过 N 元素，而当我们增加 j 时，我们只会跳过一个元素.因此，循环的迭代 (i, j) 将映射到线性化循环顺序中的位置 i * N + j。这意味着在 i * N + j 迭代中，我们想要访问 (i, j)。为此，我们可以使用一些简单的算法从索引中恢复 i 和 j。如果k是当前循环计数器，我们要访问

i = k / N   (integer division)
j = k % N

因此循环可以写成

for (int k = 0; k < N * N; ++k) {
    int i = k / N;
    int j = k % N;
}

但是，您必须小心，因为 N * N 可能不适合整数，因此可能会溢出。在这种情况下，您可能希望求助于双 for 循环。此外，额外除法和模数的引入将使该代码运行(可能)比双 for 循环慢得多。最后，这段代码比原始代码更难阅读，您需要确保提供积极的注释来描述您在这里所做的事情。同样，我强烈建议您根本不要这样做，除非您有非常充分的理由怀疑标准双 for 循环存在问题。

(有趣的是，这里使用的技巧也可以用于使用一维数组来表示多维数组。逻辑是相同的——你有一个二维结构，你想用一维结构来表示。 )

希望这对您有所帮助!