c++ - 在C++中枚举k维超立方体顶点的最有效方法是什么？

基本问题:我有一个k维框。我有一个上限和下限的 vector 。枚举顶点坐标的最有效方法是什么？

背景:例如，假设我有一个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对应于下界 vector 的第0个元素，同样U_2是上界 vector 的第二个元素。

我的代码:

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);

但是我已经对其进行了预先调整大小，以免浪费时间在分配内存的循环中。每次我运行算法时，我都需要调用上述过程约5000万次-因此，我需要它真正有效。

可能的子问题:向k移位而不是总是向1移位并存储中间结果是否趋于更快？ (我应该使用>> = ??吗？)

最佳答案

如果可以减少条件分支，它可能会运行得更快:

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

如果可以在单个数组中交织上限和下限，则可能会进一步改善性能:

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

我不知道逐步转移idx是否有帮助。它很容易实现，因此值得一试。

关于c++ - 在C++中枚举k维超立方体顶点的最有效方法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4373118/