5

基本的な質問： 私はak次元ボックスを持っています。上界と下界のベク​​トルがあります。頂点の座標を列挙する最も効率的な方法は何ですか？

背景： 例として、3次元のボックスがあるとします。取得するのに最も効率的なアルゴリズム/コードは何ですか：

vertex[0] = ( 0, 0, 0 ) -> ( L_0, L_1, L_2 )
vertex[1] = ( 0, 0, 1 ) -> ( L_0, L_1, U_2 )
vertex[2] = ( 0, 1, 0 ) -> ( L_0, U_1, L_2 )
vertex[3] = ( 0, 1, 1 ) -> ( L_0, U_1, U_2 )

vertex[4] = ( 1, 0, 0 ) -> ( U_0, L_1, L_2 )
vertex[5] = ( 1, 0, 1 ) -> ( U_0, L_1, U_2 )
vertex[6] = ( 1, 1, 0 ) -> ( U_0, U_1, L_2 )
vertex[7] = ( 1, 1, 1 ) -> ( U_0, U_1, U_2 )

ここで、L_0は下限ベクトルの0番目の要素に対応し、同様にU_2は上限ベクトルの2番目の要素です。

私のコード：

const unsigned int nVertices = ((unsigned int)(floor(std::pow( 2.0, double(nDimensions)))));

for ( unsigned int idx=0; idx < nVertices; ++idx )
{
   for ( unsigned int k=0; k < nDimensions; ++k )
   {
      if ( 0x00000001 & (idx >> k) )
      {
         bound[idx][k] = upperBound[k];
      }
      else
      {
         bound[idx][k] = lowerBound[k];
      }
   }
}

ここで、変数boundは次のように宣言されています。

std::vector< std::vector<double> > bound(nVertices);

ただし、メモリを割り当てるループで時間を無駄にしないように、事前にサイズを設定しました。アルゴリズムを実行するたびに上記のプロシージャを約50,000,000回呼び出す必要があるため、これを非常に効率的に行う必要があります。

考えられるサブ質問：常に1ずつシフトして中間結果を保存するよりも、kだけシフトする方が速い傾向がありますか？（>> = ??を使用する必要があります）

4

1 に答える 1

4

条件分岐を減らすことができれば、おそらく速くなります。

bound[idx][k] = upperLowerBounds[(idx >> k) & 1][k];

単一の配列で上限と下限をインターリーブできる場合は、さらに改善される可能性があります。

bound[idx][k] = upperLowerBounds[(k << 1) | (idx >> k)&1];

idx少しずつシフトすることが役立つかどうかはわかりません。実装は簡単なので、試してみる価値があります。

于 2010-12-07T03:44:19.043 に答える