在C ++中枚举k维超立方体顶点的最有效的方法是什么? [英] What is the most efficient way to enumerate vertices of k dimensional hypercube in C++?
问题描述
基本问题:我有一个三维框。我有一个上限和下限的向量。什么是枚举顶点坐标的最有效的方法?
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?
背景:举个例子,说我有一个三维框。什么是最有效的算法/代码来获得:
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是上界向量的第二个元素。
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.
我的代码:
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];
}
}
}
$ c> bound 声明为:
where the variable bound
is declared as:
std::vector< std::vector<double> > bound(nVertices);
但我已经预先设置它,以免浪费时间在循环分配内存。我需要在每次运行我的算法时调用上述过程大约50,000,000次 - 所以我需要这是真的有效率。
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 >>= ??)
推荐答案
如果你可以减少条件分支, p>
It will probably go faster if you can reduce conditional branching:
bound[idx][k] = upperLowerBounds[(idx >> k) & 1][k];
如果可以在单个数组中交叉上下边界, / p>
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 ++中枚举k维超立方体顶点的最有效的方法是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!