K boyutlu hiperküpün köşe noktalarını C++ olarak numaralandırmanın en etkili yolu nedir?

Question

Temel Soru: K boyutlu bir kutum var. Üst sınırların ve alt sınırların bir vektörü var. Köşelerin koordinatlarını sıralamak için en etkili yol hangisidir?

Arka plan: Örneğin, 3 boyutlu bir kutu olduğunu varsayalım. L_0 alt sınır vektör & arasında 0'th elemanına karşılık gelen

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) 

aynı şekilde U_2 üst sınır vektörünün 2 elemanıdır: elde etmek için en verimli bir algoritma/kod ne.

Benim Kod:

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

gibi değişken bound bildirildi: Ben önceden büyüklüğünde döngü tahsis bellekte zaman israf olmamak için ettik

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

ama . Algoritimi her çalıştırdığımda yukarıdaki prosedürü 50.000.000 kez çağırmam gerekiyor - bu yüzden gerçekten verimli olmak için buna ihtiyacım var.

Muhtemel Alt Soru: Her zaman 1'e geçmek yerine bir ara sonucu saklamak yerine k ile daha hızlı geçiş yapma eğiliminde mi? Eğer koşullu dallanma azaltabilir eğer

Answer 1

Muhtemelen daha hızlı gidecek (Ben ?? = >> kullanarak olmalı): Sen de alt ve üst sınırları serpiştirebilir bile daha fazla şeyler geliştirecek

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

tek bir dizi: idx kayması aşamalı yardım ederse

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

bilmiyorum. Uygulaması için yeterince basit, bu yüzden denemeye değer.