迭代任意维度数组的最快方法是什么？

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（）算法是：

我能想到的最快的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];
    }
}

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

是否有更快的算法？

- Brendan Hill

---

你有测量运行时间吗？ doSomething(x, y, z ...) 很快吗？你的第一个版本（3个for循环）不应该被任何好的编译器展开吗？ - tgmath

tgmath - 是的，编译器可能会展开一个硬编码为3级的循环，但我需要一个N级循环，其中N在编译时不知道，而且我目前正在处理100万次以上的迭代，这是无法展开的。我对迭代算法的优化比doSomething()的优化更感兴趣。 - Brendan Hill

Answer 1

除非你开始做一些类似于格雷码的事情，这将改变你的遍历顺序（并且可能非常复杂），否则你所能达到的就是最好的状态。实际上，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检查，并允许您的iterate函数在运行时更改布尔值，当它耗尽可以增加的维度时。 这将使您的for循环减少到while（keepGoing）{...}。
• 传递包含每个维度最小和最大值的结构数组可能会快一点，但我预计缓存会完全抵消这些好处。

当然，在进行任何此类更改之前，请先进行基准测试-每种架构和工具链的反应都不同。

- Kaganar

---

感谢您的反馈！ - Brendan Hill