4

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

IE。一个通用的解决方案：

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

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

有更快的算法吗？

4

1 回答 1

3

除非你开始做一些类似于格雷码的事情，这会改变你的遍历顺序（并且可能非常复杂），否则你几乎已经达到了它所能达到的水平。实际上， 的摊销时间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，你可以使用模板。）
  • 实际上，您可以在大外部循环（其中有调用的那个）中摆脱您的 maxIterations/iteration 检查，doSomething并允许您的迭代函数在它用完可以增加的维度时更改布尔值。这会将您的for循环减少到while (keepGoing) { ... }.
  • 传递具有每个维度的最小值和最大值的结构数组可能会稍微快一些，但我希望缓存几乎可以完全减轻这些好处。

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

于 2014-11-10T15:31:57.877 回答