What is the most efficient way to list the vertices of a k-dimensional hypercube in C ++?

Question

The main question: I have a size square. I have a vector of upper and lower bounds. What is the most efficient way to list vertex coordinates?

Background: As an example, let's say that I have a 3-dimensional box. What is the most efficient algorithm / code to get:

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 0th element of the lower bound vector, and U_2 - the 2nd element of the upper boundary vector.

My code is:

 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 bound variable is declared as:

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

but I predefined it so as not to waste time allocating memory. I need to call the above procedure about 50,000,000 times every time I run my algorithm, so I need it to be really effective.

Possible subheadings:. Most likely, there is a transition to k instead of always shifting by 1 and preserving the intermediate result? (Should I use → = ??)

Answer 1

This will most likely happen faster if you can reduce conditional branching:

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

You can improve the situation even more if you can alternate the upper and lower boundaries in one array:

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

I do not know if idx value can change. It's easy enough to implement, so it’s worth a try.