优化嵌套循环的算法

Question

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

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

• 双方i并j从0开始
• 两个循环都以相同的条件结束
• 双方i并j都以相同的速度递增

这可以在一个循环中以某种方式完成吗？

Answer 1

这是可能使用一个循环来写这篇文章,但我强烈建议不这样做.双循环是一个成熟的习惯,程序员知道如何阅读,如果你将两个循环折叠成一个,你就牺牲了可读性.此外,目前还不清楚这是否会使代码运行得更快,因为编译器已经非常擅长优化循环.将两个循环折叠成一个循环需要在每个步骤进行一些额外的数学计算,这几乎肯定比两个循环独立地慢.

也就是说,如果你想把它写成一个循环,一个想法是考虑迭代空间,你迭代的对的集合.现在,看起来像这样:

(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循环有问题.

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

希望这可以帮助!

Answer 2

没有办法显着优化循环本身。然而，当你考虑到“用 i 和 j 做某事”的细节时，i 或 j 是外循环会产生很大的不同。例如，一个顺序可能导致在内存或磁盘中大量跳转，而另一个顺序导致顺序访问，或几乎如此。

此外，有时您可以通过将不依赖于内部索引的计算从内部循环移动到外部循环来优化双循环，可能使用临时变量。智能编译器可能会将其优化到一定程度，但它们并不完美。