c++ - 迭代任意范围的 n 维数组的最快方法？

Question

在 C++ 中，我希望迭代一个 n 维数组，其范围分别从 min[n] 到 max[n]，并在整个过程中分别保持 ord[n] 中的纵坐标。

即。通用解决方案:

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 ...)

形式:

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)

我能想到的 iterate() 最快的算法是:

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];
    }
}

这会根据需要递增和重置每个纵坐标，避免调用堆栈或任何数学运算。

有没有更快的算法？

Answer 1

除非你开始做类似于 Gray codes 的事情这将改变你的遍历顺序(并且可能非常复杂)，你几乎处于它将会达到的最佳状态。实际上，iterate 的摊销时间已经是 O(1)，假设每个维度都有一个不等于其最大值的最小值。

最坏的情况是所有 d 维度都有 maximum = minimum + 1。也就是说，任何特定维度的每隔一个增量都会溢出到下一个维度。但是，请注意特定维度 x(从 1 到 d)所需的数字更改总数为 2^( d + 1 - x) - 1。这显然小于 2^(d + 1 - x)。对所有维度(1 到 d)求和是一个简单的几何求和，它产生 2^(d + 1) - 2 这显然是小于 2^(d + 1)。请注意迭代次数是 2^d，因此每次迭代的平均时间是一个常数:2^(d + 1)/2^d = 2。

如果您真的需要压缩速度，最好的办法可能是低级别的调整:

• 维数是否已知且小于一个小(例如，20 或更少)常量？然后，您可以通过展开循环来消除 for 循环。如果您的编译器可以推断出 dimensions 是常量，那么您的编译器可能已经足够聪明地执行此操作，或者您可能必须创建多个版本的 iterate 具有常量维度或手动展开循环。 (如果你想给它一个很好的 API，你可以使用模板。)
• 实际上，您可以在大 外循环(其中包含doSomething 调用的循环)中摆脱 maxIterations/iteration 检查，并允许迭代函数当它用完它可以增加的维度时改变一个 bool 值。这会将您的 for 循环减少为 while (keepGoing) { ... }。
• 传递具有每个维度的最小值和最大值的结构数组可能会稍微快一些，但我希望缓存几乎可以完全抵消优势。

当然，在任何此类更改之前和之后进行基准测试——每个架构和工具链的 react 都不同。