4

C++ では、それぞれ min[n] から max[n] までの範囲の任意の範囲で 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];
    }
}

これにより、必要に応じて各縦座標がインクリメントおよびリセットされ、コールスタックや計算が回避されます。

より高速なアルゴリズムはありますか?

4

1 に答える 1

3

トラバーサルの順序を変更する (そして非常に複雑になる可能性がある)グレイ コードに類似したことを開始しない限り、ほとんどの場合、それが得られるのと同じくらい良い点に達しています。実際、各次元の最小値が最大値と等しくないと仮定すると、 の償却時間iterateはすでにです。O(1)

最悪のケースは、すべてのd寸法に がある場合ですmaximum = minimum + 1。つまり、特定の次元の 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増加できる次元がなくなったときに iterate 関数がブール値を変更できるようにすることができます。これにより、forループが に減少しますwhile (keepGoing) { ... }。
  • 各次元の最小値と最大値を持つ構造体の配列を渡す方がわずかに高速かもしれませんが、キャッシュによってその利点がほぼ完全に軽減されると予想しています。

もちろん、そのような変更の前後のベンチマークでは、すべてのアーキテクチャとツール チェーンの反応が異なります。

于 2014-11-10T15:31:57.877 に答える