0

次のネストされたループ計算があります。

int aY=a*Y,aX=a*X;
for(int i=0; i<aY; i+=a)
{
    for(int j=0; j<aX; j+=a)
    {
        xInd=i-j+offX;
        yInd=i+j+offY;
        if ((xInd>=0) && (xInd<X) &&
            (yInd>=0) && (yInd<Y) )
            {
             z=yInd*X+xInd;
            //use z
            }
     }
}

i、、jへの依存xIndをできるだけなくしたいyInd。言い換えると、ループの実行中に受け取るすべての値を「トラバース」したいのですが、変数、、、および-zを支援する必要はありません。または、少なくとも最小限の数の計算が必要です（最も重要なのは乗算がないことです）。どうやってやるの？ループをより効率的にするための可能な方法に関する他のヒントを歓迎します。ありがとう！ijxIndyInd

4

2 に答える 2

0

offX と offY が 0 であると仮定し、'<' を '<=' に置き換えると、次のようにして i と j を取り除くことができます。

for (yInd = 0; yInd <= aX + aY; ++yInd)
    for (xInd = max(-yInd, -aX); xInd <= min(yInd, aY); ++xInd)
于 2013-01-12T14:49:59.833 に答える
0

ループの反復回数を最小限に抑える方法として質問を読むと、次のアプローチを取ることができます。

制約:

(xInd>=0) && (xInd<X)
(yInd>=0) && (yInd<Y)

for ループの境界を狭めるために使用できるようにします。展開xIndしてyInd与える：

0 <= i - j + offX <= X
0 <= i + j + offY <= Y

修正iすると、2 番目のループ境界を次のように書き換えることができます。

for(int i=0; i<aY; i+=a) {
    int lower = (max(i + offX - X, -i - offY) / a) * a; //factored out for clarity.
    int upper = min(i + offX, Y - i -offY);
    for(int j=lower; j<=upper; j+=a) {

offX、offY、の可能な値について詳しく知っていればa、XさらにY削減できる可能性があります。

実際には、最初にプロファイリングせずにこのタイプの最適化をやみくもに適用することはおそらく望ましくないことに注意してください (コンパイラーがこれを行うのを妨げる可能性があります ( gcc グラファイトなど) )。

インデックスとして使用

値z=yInd*X+xIndがメモリのインデックスに使用されている場合は、メモリ アクセスがシーケンシャルであることを確認して、良好なキャッシュ動作を確保することで、より大きな効果が得られます。

現在yInd、反復ごとに変更されるため、キャッシュのパフォーマンスが低下する可能性があります。

この問題の解決策は、最初にすべてのインデックスを計算して保存し、次にこれらのインデックスを使用して 2 番目のパスですべてのメモリ操作を行うことです。

int indicies[Y * X];
int index = 0;
for(...){
    for(...){
        ...
        indicies[index++] = z;
    }
}
// sort indicies
for(int idx = 0; idx < index; idx++){
    z = indicies[idx];
    //do stuff with z
}
于 2013-01-12T15:02:54.580 に答える