小编典典

优化嵌套循环的算法

algorithm

是否有可用的算法来优化以下代码的性能?

for (i = 0; i < LIMIT; i++) {
  for (j = 0; j < LIMIT; j++) {
   // do something with i and j
  }
 }
  • 双方ij从0开始
  • 两个循环在相同条件下结束
  • 双方ij以同样的速度递增

可以以某种方式在1个循环中完成吗?


阅读 291

收藏
2020-07-28

共1个答案

小编典典

可能使用一个循环来写这篇文章,但我强烈建议不这样做。double
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可能不适合整数,因此可能会溢出。在这种情况下,您可能希望退回到double
for循环。此外,引入额外的除法和模将使该代码的运行(可能)比double
for循环慢。最后,此代码比原始代码难读得多,并且您需要确保提供积极的注释来描述您在这里所做的事情。再一次,我强烈建议您完全不要这样做,除非您有充分的理由怀疑标准double
for循环存在问题。

(有趣的是,这里使用的技巧也可以用于使用一维数组表示多维数组。逻辑是相同的-您具有要用一维结构表示的二维结构。)

希望这可以帮助!

2020-07-28