Каков наиболее эффективный способ перечисления вершин k-мерного гиперкуба в C ++? - PullRequest
Новая
       10

Каков наиболее эффективный способ перечисления вершин k-мерного гиперкуба в C ++?

5 голосов
/ 07 декабря 2010

Основной вопрос: У меня есть k-мерная коробка. У меня есть вектор верхних и нижних границ. Как наиболее эффективно перечислить координаты вершин?

Справочная информация: В качестве примера, скажем, у меня есть трехмерное поле. Какой наиболее эффективный алгоритм / код для получения: 

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 - 2-й элемент вектора верхней границы.

Мой код: 

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

где переменная bound объявлена ​​как: 

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

но я предварительно изменил его размер, чтобы не тратить время в цикле, выделяющем память. Мне нужно вызывать вышеупомянутую процедуру примерно 50 000 000 раз каждый раз, когда я запускаю свой алгоритм - поэтому мне нужно, чтобы это было действительно эффективно.

Возможные подвопросы: Имеет ли тенденцию быстрее сдвигаться на k вместо того, чтобы всегда сдвигаться на 1 и сохранять промежуточный результат? (Должен ли я использовать >> = ??)

1 Ответ

4 голосов
/ 07 декабря 2010

Вероятно, будет быстрее, если вы сможете уменьшить условное ветвление: 

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

Вы могли бы улучшить ситуацию еще больше, если бы вы могли чередовать верхнюю и нижнюю границы в одном массиве: 

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

Я не знаю, помогает ли смещение idx постепенно. Это достаточно просто реализовать, поэтому стоит попробовать.

...