What is better way to loop over two ranges - multiply them together and do it one loop, or loop over each range separately?

Question

I can't decide how I should loop over ranges. This way:

for (int i = 0; i < max_i; i++) {
    for (int j = 0; j < max_j; j++) {
        // first way - two loops
    }
}

Or this way:

for (int k = 0; k < max_i*max_j; k++) {
    // second way - one loop
}

Thanks, Boda Cydo.

Answer 1

Depends on what you do inside the loop. Do you need the indices i and j? Then I would prefer the first solution.

Answer 2

Well it depends. If you want seperate indexes then you can use first one. if you want just a single index then the second one.

Complexity of both loops is same.

Answer 3

If you decided to go with the first way, then everything is good because you have the values of both i and j. In the second way, you have to get the value of i and j manually:

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

So, the first way is definitely better in your case.

Answer 4

It depends on what you will be doing with the indices. If you're using two values separately (for example you're iterating over all permutations of the values in the two loops) then the two loop solution is more clear. The one-loop strategy is better if you don't care about the individual values but just their product instead.

Either way, choose the strategy which expresses your intent more clearly. The performance implications are trivial in comparison to the importance of the simplicity of maintaining the code.

Answer 5

If you use a 2D array the first one ist much more readable. In former days it was somehow common to emulate 2d arrays with a 1D, but also in this case the first is more readable.

Answer 6

Obviously, if you have the choice, you don't need the precise value of i and j during your loop.

So the second option is better, more readable (less indentations). A little optimisation you could do, ( so as not to do the multiplication on each loop iteration):

int iKMax = max_i*max_j;
for (int k = 0; k < iKMax ; ++k)  
{
    // second way - one loop
}

And always use the prefix operator in loops (++k) cause whatever the object iterated over, it saves up one copying of this object. (cf. C++ Coding Standards: 101 Rules, Guidelines, And Best Practices by Herb Sutter and, Andrei Alexandrescu )

Answer 7

You can't use second variant when max_i or/and max_j are large enough. Note that int is a signed type. If sizeof(int) is equal to 4 bytes, then in case when max_i=32768 and max_j=65536 you loop will be executed zero times.

If there are no special requirements I'd prefer the first variant since it more readable.

Answer 8

First loop is better for 2 reasons at least:

1. It could make the nested nature of the loops clear to the reader (depending on what is required)
2. What happens if max_i * max_j overflows in the second alternative?

Also please explore if loop index variables should be 'int' or 'size_t'. size_t is guaranteed to be positive always

Answer 9

When in doubt, assume that the compiler will optimize better than you.

This is definitely not true for stuff like Android 1.0, but most C/C++ compilers are reasonably good. A good compiler ought to be able to optimize simple 2D array access (e.g. summing all the values of the array) into one loop.