Fastest way to iterate over an n-dimensional array of arbitrary extents?
In C ++, I want to iterate over an n-dimensional array with arbitrary extents from min [n] to max [n] respectively, maintaining ordinates in ord [n] respectively all over the place.
Those. general solution for:
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 ...)
From 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)
Fastest algorithm for iterate () I can think of:
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 needed, avoiding challenge or any math.
Is there a faster algorithm?
source to share
Unless you start doing something similar to gray codes that changes the order of your traversal (and can be very difficult), you're pretty much at a point where it's as good as it gets. In fact, amortized time is iterate
already O(1)
assuming that each dimension has a minimum that is not equal to its maximum.
In the worst case, all sizes d
are maximum = minimum + 1
. That is, every other increment of any particular dimension will spill over into the next dimension (s). Note that the total number of digit changes required for a particular measurement 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 that yields 2^(d + 1) - 2
, which is obviously less 2^(d + 1)
. Please note that the number of iterations 2^d
, and therefore, the average time per iteration is constant: 2^(d + 1) / 2^d = 2
.
If you really need to squeeze the speed, perhaps the best it gets is the low level settings:
- Is the number of measurements known and less than a small (say 20 or less) constant? Then you can exclude the loop
for
by unrolling the loop. Your compiler may be smart enough to do this already if it can figure out whatdimensions
is constant, or you may need to create multiple versionsiterate
with constant size or with a manually unwrapped loop. (You can use a template if you want to give it a good API.) - In fact, you can get rid of the maxIterations / iteration checks in a big outer loop (the one that has a call in it
doSomething
) and lets your iteration function change the boolean when it ends up in dimensions that it can increment.This will shorten the loopfor
towhile (keepGoing) { ... }
. - It might be very slightly faster to pass an array of structures with each minimum and maximum size, but I expect the cache to mitigate the benefits almost entirely.
Of course, the benchmark before and after any such changes - each architecture and tool chain reacts differently.
source to share