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

Question

基本问题：我有一个k维的盒子。我有一个上界和下界的向量。如何最有效地枚举顶点的坐标？

背景：以三维盒子为例，如何获得最有效的算法/代码：

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

但是我已经预先调整了大小，以免在循环中分配内存浪费时间。每次运行算法时，我需要调用上述过程大约5000万次--所以我需要这个过程真正高效。

可能的子问题：移位k位是否比始终移位1位并存储中间结果更快？（我应该使用“>>=”吗？）

- M. Tibbits

---

你对在汇编语言中探究有多大的反感？ 还有一件事：性能分析，性能分析，性能分析。采纳这里的建议并进行测试，看看它们在哪些地方快，在哪些地方慢。 - Theo Belaire

我已经使用MSVS 2005和Vtune对代码进行了分析。我很乐意使用汇编语言 - 尽管我会编译到各种目标，所以我更注重算法建议而不是特定于架构的建议，但如果它真的很好，那就更好了！-- 我应该注意：主要针对Xeon X5550和Core i7 930目标。 - M. Tibbits

K不是固定的。我目前正在使用k = 25、50、100、500分析数据集。 - M. Tibbits

啊，你说得对，我一下子做了太多事情了。 我现在正在进行 k = 25、50、75 和 100 的操作。但是我突然想到我一直在使用无符号整数编码，因此将被限制在 64 维。 嗯。 - M. Tibbits

另外，如果您使用size_t而不是unsigned int，您将能够访问系统内存可以容纳的所有元素。 - Emile Cormier

Answer 1

如果你能减少条件分支，那么速度可能会更快：

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

你可以在一个数组中交错地放置上下限，这样可以进一步提高效率。

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

我不确定逐步增加idx是否有帮助。它很容易实现，所以值得一试。

- Marcelo Cantos

---

我第一次实现你的建议，让我的性能提高了40％。谢谢！ - M. Tibbits