0

M行N列の行列があり、要素のバイト配列として割り当てられているM*N場合（これらの要素は最初はゼロに設定されています）、次のルールに従ってこの行列を変更します。特定の要素を特定の値に設定する必要があります。言い換えると、行列が与えられた場合、行列の領域を設定する必要があります。この目的のために、配列の連続していない部分にアクセスする必要があります。

上記の操作を実行するために、私は次の情報にアクセスできます。

  • 近傍の中心にある要素へのポインター（上記の操作中にこのポインターを変更してはなりません）。この要素の位置（行と列）も提供されます。
  • 近傍のサイズL*L（Lは常に奇数です）。

この操作を実装するコードは、C ++で可能な限り高速に実行する必要があります。このため、上記のポインターを使用して配列のさまざまな部分にアクセスすることを考えました。代わりに、近傍の中央要素の位置（行と列）により、指定された領域が行列の次元を超えているかどうかを確認できます（たとえば、領域の中心が行列の端にある場合があります） ：この場合、マトリックス内にある領域のその部分のみを設定する必要があります。

int M = ... // number of matrix rows
int N = ... // number of matrix columns

char* centerPtr = ... // pointer to the center of the region
int i = ... // position of the central element
int j = ... // of the region to be modified

char* tempPtr = centerPtr - (N+1)*L/2;
for(int k=0; k < L; k++)
{
    memset(tempPtr,value,N);
    tempPtr += N;
}

どうすればコードを改善できますか？1つの領域が行列の次元を超える可能性があるという事実をどのように処理しますか？実行時間に関してコードをより効率的にする方法は？

4

1 に答える 1

1

あなたのコードは、領域がマトリックスの外側と重ならない一般的なケースにおそらく最適です。この種のコードで発生する可能性のある主な効率の問題は、行ではなく列に外側のループを作成することです。これにより、キャッシュとページングのパフォーマンスが低下します。あなたはそれをしていません。

最近のほとんどのコンパイラでは、ポインタを使用しても速度の利点はほとんどまたはまったくありません。オプティマイザーは、通常の配列インデックスから非常に優れたポインターコードを考え出します。場合によっては、配列のインデックスコードが、同じことを行うために手動で調整したポインタコードよりも大幅に高速に実行されることを確認しました。したがって、インデックス演算がより明確な場合は、ポインタ演算を使用しないでください。

北、北西、西、...、北東の8つの境界ケースがあります。これらのそれぞれは、適切な要素に触れるためにループのカスタムバージョンを必要とします。北西のケースを示し、残りを解決させます。

ケースを処理するための最速の方法は、3レベルの「if」ツリーです。

if (j < L/2) {  // northwest, west, or southwest
  if (i < L/2) {  
    // northwest
    char* tempPtr = centerPtr - (L/2 - i) * N - (L/2 - j);
    for(int k = 0; k < L; k++) {
      memset(tempPtr, value, L - j);
      tempPtr += N;
    }
  } else if (i >= M - L/2) { 
    // southwest
  } else { 
    // west
  }
} else if (j >= N - L/2) { // symmetrical cases for east.
  if (i < L/2) {  
    // northeast
  } else if (i >= M - L/2) { 
    // southeast
  } else { 
    // east
  }
} else { 
  if (i < L/2) {  
    // north
  } else if (i >= M - L/2) { 
    // south
  } else { 
    // no overlap
  }
}

このようにするのは面倒ですが、地域ごとに比較できるのは3つまでです。

于 2013-01-20T07:10:28.160 に答える