What is the most efficient way to enumerate vertices of k dimensional hypercube in C++?
binary, bit-shift, c++, enumeration
Solution
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];
I don't know if shifting `idx` incrementally helps. It's simple enough to implement, so it's worth a try.
Problem
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 ) ``` 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. My 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]; } } } ``` where the variable `bound` is declared as: ``` std::vector< std::vector<double> > bound(nVertices); ``` 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. 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 >>= ??)