是否有可用的算法来优化以下代码的性能?
for (i = 0; i < LIMIT; i++) { for (j = 0; j < LIMIT; j++) { // do something with i and j } }
i
j
可以以某种方式在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是当前循环计数器,我们要访问
(0, 0), (0, 1), ..., (0, N-1), (1, 0), (1, 1), ..., (1, N-1), ..., (N-1, 0), (N-1, 1), ..., (N-1, N-1)
N
(i, j)
i * N + 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循环存在问题。
N * N
(有趣的是,这里使用的技巧也可以用于使用一维数组表示多维数组。逻辑是相同的-您具有要用一维结构表示的二维结构。)
希望这可以帮助!