4

In C++ I wish to iterate an n-dimensional array with arbitrary extents ranging from min[n] to max[n] respectively, maintaining the ordinates in ord[n] respectively throughout.

Ie. a general solution to:

for (int x = 0; x < 10; x++)
for (int y = 3; y < 20; y++)
for (int z = -2; z < 5; z++)
...
   doSomething(x, y, z ...)

Of the form:

int min[n] {0,  3, -2 ...}
int max[n] {10, 20, 5 ...}
int ord[n] {0,  0,  0 ...};

int maxIterations = (max[0] - min[0]) * (max[1] - min[1]) * ....
for (int iteration = 0; iteration < maxIterations; iteration++)
   doSomething(ord)
   iterate(n, ord, min, max)

The fastest algorithm for iterate() I can think of is:

inline void iterate(int dimensions, int* ordinates, int* minimums, int* maximums)
{
    // iterate over dimensions in reverse...
    for (int dimension = dimensions - 1; dimension >= 0; dimension--)
    {

        if (ordinates[dimension] < maximums[dimension])
        {
            // If this dimension can handle another increment... then done.
            ordinates[dimension]++;
            break;
        }

        // Otherwise, reset this dimension and bubble up to the next dimension to take a look
        ordinates[dimension] = minimums[dimension];
    }
}

This increments and resets each ordinate as required, avoiding the callstack or any maths.

Is there are faster algorithm?

Brendan Hill
  • 3,406
  • 4
  • 32
  • 61
  • Have you measured the running time? Is `doSomething(x, y, z ...)` very fast? Shouldn't your first version (3 for loop) be unrolled by any decent compiler? – tgmath Nov 10 '14 at 13:04
  • tgmath - yes a compiler might unroll a loop hard coded to 3 levels but I need a N-level loops where N is not known at compile time, plus I am currently working with 1 million+ iterations which could not be unrolled. I am interested in the optimization of the iterating algorithm rather than the optimization of doSomething(). – Brendan Hill Nov 11 '14 at 23:35

1 Answers1

3

Unless you start doing something analogous to Gray codes which is going to change the order of your traversal (and potentially be very complex), you're pretty much at a point where it's as good as it's going to get. Actually, the amortized time of iterate is already O(1), assuming each dimension has a minimum that is not equal to its maximum.

The worst case is when all d dimensions have maximum = minimum + 1. That is, every other increment of any particular dimension will spill into the next dimension(s). However, note that the total number of digit changes needed for a specific dimension x (from 1 to d) is 2^(d + 1 - x) - 1. This is obviously less than 2^(d + 1 - x). Summing this over all dimensions (1 through d) is a simple geometric sum which yields 2^(d + 1) - 2 which is obviously less than 2^(d + 1). Note the number of iterations is 2^d, and hence the average time per iteration is a constant: 2^(d + 1) / 2^d = 2.

If you really have to squeeze speed, probably the best it's going to get is low level tweaks:

  • Is the number of dimensions known and less than a small (say, 20 or less) constant? Then you can eliminate the for loop by unrolling the loop. Your compiler may be smart enough to do this already if it can deduce that dimensions is constant, or you may have to create several versions of iterate with a constant dimension or with the loop unrolled manually. (You could use templating if you wanted to give it a nice API.)
  • You can actually get rid of your maxIterations/iteration check in the big outer loop (the one that has the doSomething call in it) and allow your iterate function to change a boolean when it runs out of dimensions it can increase. This reduces your for loop to while (keepGoing) { ... }.
  • It may be very slightly faster to pass an array of structures with each dimension's minimum and maximum, but I expect cache to mitigate the benefits almost entirely.

Of course, benchmark before and after any such changes -- every architecture and tool chain reacts differently.

Kaganar
  • 6,540
  • 2
  • 26
  • 59