¿Cuál es la manera más eficiente de enumerar vértices de hipercubo k dimensional en C++?

Question

Pregunta básica: Tengo una caja dimensional k. Tengo un vector de límites superiores y límites inferiores. ¿Cuál es la forma más eficiente de enumerar las coordenadas de los vértices?

Antecedentes: Como ejemplo, supongo que tengo una caja tridimensional. ¿Cuál es el algoritmo/código más eficiente para obtener:

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) 

donde L_0 corresponde al elemento de orden 0 de la vector límite inferior & igualmente U_2 es ​​el segundo elemento del vector límite superior.

Mi Código:

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

donde la variable bound se declara como:

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

pero tengo pre-tamaño que a fin de no perder el tiempo en la memoria de asignación de bucle . Necesito llamar al procedimiento anterior unas 50,000,000 de veces cada vez que ejecuto mi algoritmo, así que necesito que esto sea realmente eficiente.

Posibles Subpreguntas: ¿Tiende a ser más rápido cambiar por k en lugar de cambiar siempre por 1 y almacenar un resultado intermedio? (¿Debo estar utilizando >> = ??)

Answer 1

es probable que vaya más rápido si se puede reducir la bifurcación condicional:

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

Es posible mejorar las cosas aún más si se puede intercalar los límites superior e inferior en una sola matriz:

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

no sé si el cambio incremental idx ayuda. Es lo suficientemente simple de implementar, por lo que vale la pena intentarlo.