什么是枚举ķ维超立方体的顶点在​​C ++中最有效的方法是什么? [英] What is the most efficient way to enumerate vertices of k dimensional hypercube in C++?

查看:115
本文介绍了什么是枚举ķ维超立方体的顶点在​​C ++中最有效的方法是什么?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

基本问题:我有A K维框。我有上限和下限的向量。什么是枚举顶点的坐标的最有效方法是什么?

Basic Question: I have a k dimensional box. I have a vector of upper bounds and lower bounds. What is the most efficient way to enumerate the coordinates of the vertices?

背景:作为一个例子,说我有一个三维的盒子。什么是最有效的算法/ code获得:

Background: As an example, say I have a 3 dimensional box. What is the most efficient algorithm / code to obtain:

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元素

where L_0 corresponds to the 0'th element of the lower bound vector & likewise U_2 is the 2nd element of the upper bound vector.

我的code:

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];
      }
   }
}

其中的变量约束被声明为:

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

但我一直在循环中分配内存pre大小的它,以免浪费时间。我需要每次运行我的算法时间打电话约5000万次以上过程 - 所以我需要这是真正有效

but I've pre-sized it so as not to waste time in the loop allocating memory. I need to call the above procedure about 50,000,000 times every time I run my algorithm -- so I need this to be really efficient.

可能的子问题:是否倾向于更快地被K转移,而不是总是由1移位和保存中间结果? (我应该使用>> =?)

Possible Sub-Questions: Does it tend to be faster to shift by k instead of always shifting by 1 and storing an intermediate result? (Should I be using >>= ??)

推荐答案

这可能会走得更快,如果你可以减少条件分支:

It will probably go faster if you can reduce conditional branching:

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

您可能会改善的事情甚至更多,如果你能在交错单个阵列的上限和下限:

You might improve things even more if you can interleave the upper and lower bounds in a single array:

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

我不知道,如果移 IDX 逐步帮助。这是很简单的实现,所以这是值得一试。

I don't know if shifting idx incrementally helps. It's simple enough to implement, so it's worth a try.

这篇关于什么是枚举ķ维超立方体的顶点在​​C ++中最有效的方法是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆