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 次——所以我需要这个过程非常有效。

可能的子问题：移动k而不是总是移动1并存储中间结果是否会更快？（我应该使用 >>= 吗？？）

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 回答