优化嵌套循环的算法 [英] Algorithm to optimize nested loops
问题描述
是否有算法可用于优化以下性能？
for（i = 0; i< LIMIT ; i ++）{
for（j = 0; j
}
-
i和<$ c $
- 两个循环以相同的条件结束
- 两个
i和j以相同的比率递增
这可以在1循环中完成吗？
循环，但我强烈建议不要这样做。双循环是程序员知道如何阅读的一个成熟的习惯用法，如果你把两个循环合并成一个，你就牺牲了可读性。而且，由于编译器已经非常擅长优化循环，所以目前还不清楚这是否会使代码运行得更快。将两个循环合并成一个循环需要在每一步中额外计算几乎肯定比两个独立循环慢。
也就是说，如果你想把它写成一个单一的循环，一个想法是考虑迭代空间，你迭代的一组对。现在看起来像这样：
$ $ $ $ $ $ $ $（0,0）（0,1），（0，2），。 （1，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）， （1，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（整数除法）
j = k％N
写成
for（int k = 0; k
int j = k％N;
$ b 然而，你必须小心，因为 N * N 可能不适合整数，因此可能会溢出。在这种情况下，你会想回到双循环。此外，引入额外的分割和模数将使这个代码运行（可能）比双for循环慢得多。最后，这段代码比原来的代码更难阅读，你需要确保提供一些积极的评论来描述你在这里做什么。同样，我强烈建议你不要这样做，除非你有非常强烈的理由怀疑标准双重for循环有问题。
（有趣的是，这里使用的技巧也可以用来表示使用一维数组的多维数组。逻辑是相同的 - 你有一个二维结构，你想用一维结构来表示。）
希望这有助于！
Is there an algorithm available to optimize the performance of the following?
for (i = 0; i < LIMIT; i++) {
for (j = 0; j < LIMIT; j++) {
// do something with i and j
}
}
- Both
i and j start at 0
- Both loops end on the same condition
- Both
i and j are incremented at the same rate
Can this be done in 1 loop somehow?
解决方案 It is possible to write this using one loop, but I would strongly suggest not doing so. The double for-loop is a well-established idiom that programmers know how to read, and if you collapse the two loops into one you sacrifice readability. Moreover, it's unclear if this will actually make the code run any faster, since the compiler is already very good at optimizing loops. Collapsing the two loops into one requires some extra math at each step that is almost certainly slower than the two loops independently.
That said, if you do want to write this as a single loop, one idea is to think about the iteration space, the set of pairs that you iterate over. Right now, that looks like this:
(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)
The idea is to try to visit all of these pairs in the order (0, 0), (0, 1), ..., (0, N-1), (1, 0), (1, 1), ..., (1, N-1), ..., (N-1, 0), (N-1, 1), ..., (N-1, N-1). To do this, note that every time we increment i, we skip over N elements, while when we increment j we skip over just one element. Consequently, iteration (i, j) of the loop will map to position i * N + j in the linearized loop ordering. This means that on iteration i * N + j, we want to visit (i, j). To do this, we can recover i and j from the index using some simple arithmetic. If k is the current loop counter, we want to visit
i = k / N (integer division)
j = k % N
Thus the loop can be written as
for (int k = 0; k < N * N; ++k) {
int i = k / N;
int j = k % N;
}
However, you have to be careful with this because N * N might not fit into an integer and thus could overflow. In that case, you would want to fall back on the double for-loop. Moreover, the introduction of the extra divisions and moduli will make this code run (potentially) much slower than the double for-loop. Finally, this code is much harder to read than the original code, and you'd need to be sure to provide aggressive comments describing what it is that you're doing here. Again, I strongly advise you not to do this at all unless you have a very strong reason to suspect that there is a problem with the standard double for-loop.
(Interestingly, the trick used here can also be used to represent a multidimensional array using a single-dimensional array. The logic is identical - you have a two-dimensional structure that you want to represent with a one-dimensional structure.)
Hope this helps!
这篇关于优化嵌套循环的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
