Быстрое процентиль в C++

Question

Моя программа вычисляет моделирование методом Монте-Карло для метрики значения риска. Для упрощения, насколько это возможно, у меня есть:

1/ simulated daily cashflows 
2/ to get a sample of a possible 1-year cashflow, 
    I need to draw 365 random daily cashflows and sum them 

Следовательно, ежедневные денежные потоки являются эмпирический данной функцией distrobution для отбора проб 365 раз. Для этого я

1/ sort the daily cashflows into an array called *this->distro* 
2/ calculate 365 percentiles corresponding to random probabilities 

мне нужно сделать это моделирование годового денежного потока, скажем, 10K раз, чтобы получить популяцию моделируемых ежегодных денежных потоков для работы с. Имея функцию распределения ежедневных денежных потоков, полученных, я выборка как ...

for (unsigned int idxSim = 0; idxSim < _g.xSimulationCount; idxSim++) 
{ 
    generatedVal = 0.0; 
    for (register unsigned int idxDay = 0; idxDay < 365; idxDay ++) 
    { 
     prob = (FLT_TYPE)fastrand();   // prob [0,1] 
     dIdx = prob * dMaxDistroIndex;  // scale prob to distro function size 
              // to get an index into distro array 
     _floor = ((FLT_TYPE)(long)dIdx);  // fast version of floor 
     _ceil = _floor + 1.0f;    // 'fast' ceil:) 
     iIdx1 = (unsigned int)(_floor); 
     iIdx2 = iIdx1 + 1; 

     // interpolation per se 
     generatedVal += this->distro[iIdx1]*(_ceil - dIdx ); 
     generatedVal += this->distro[iIdx2]*(dIdx - _floor); 
    } 
    this->yearlyCashflows[idxSim] = generatedVal ; 
} 

Код внутри обоих for циклов делает линейной интерполяции. Если, скажем, 1000 долларов США соответствует prob = 0,01, 10000 долларов США соответствует prob = 0,1, то, если у меня нет эмпирического числа для p = 0,05, я хочу получить 5000 долларов США путем интерполяции.

Вопрос: этот код работает правильно, хотя профайлер говорит, что программа тратит около 60% времени выполнения на интерполяцию как таковую. Поэтому мой вопрос: как я могу сделать эту задачу быстрее? Примеры среды выполнения сообщенные VTune для конкретных линий следующим образом:

prob = (FLT_TYPE)fastrand();   // 0.727s 
dIdx = prob * dMaxDistroIndex;  // 1.435s 
_floor = ((FLT_TYPE)(long)dIdx);  // 0.718s 
_ceil = _floor + 1.0f;    // - 

iIdx1 = (unsigned int)(_floor); // 4.949s 
iIdx2 = iIdx1 + 1;     // - 

// interpolation per se 
generatedVal += this->distro[iIdx1]*(_ceil - dIdx ); // - 
generatedVal += this->distro[iIdx2]*(dIdx - _floor); // 12.704s 

прочерки означают профилировщика отчеты не Runtimes для этих линий.

Подсказка будет принята с благодарностью. Daniel

EDIT: Оба c.fogelklou и MSalters указали большие улучшения. Лучший код в соответствии с чем c.fogelklou сказанное

converter = distroDimension/(FLT_TYPE)(RAND_MAX + 1) 
for (unsigned int idxSim = 0; idxSim < _g.xSimulationCount; idxSim++) 
{ 
    generatedVal = 0.0; 
    for (register unsigned int idxDay = 0; idxDay < 365; idxDay ++) 
    { 
     dIdx = (FLT_TYPE)fastrand() * converter; 
     iIdx1 = (unsigned long)dIdx); 
     _floor = (FLT_TYPE)iIdx1; 
     generatedVal += this->distro[iIdx1] + this->diffs[iIdx1] *(dIdx - _floor); 
    } 
} 

и лучшее, что я есть вдоль линий MSalter является

normalizer = 1.0/(FLT_TYPE)(RAND_MAX + 1); 
for (unsigned int idxSim = 0; idxSim < _g.xSimulationCount; idxSim++) 
{ 
    generatedVal = 0.0; 
    for (register unsigned int idxDay = 0; idxDay < 365; idxDay ++) 
    { 
     dIdx = (FLT_TYPE)fastrand()* normalizer ; 
     iIdx1 = fastrand() % _g.xDayCount; 
     generatedVal += this->distro[iIdx1]; 
     generatedVal += this->diffs[iIdx1]*dIdx; 
    } 
} 

второй код ок. На 30% быстрее. Теперь, из 95 с общей продолжительности работы, последняя строка потребляет 68 секунд. Последняя, ​​но одна строка потребляет всего 3,2 с, поэтому двойное двойное умножение должно быть дьяволом. Я думал о SSE - сохраняя последние три операнда в массиве, а затем выполнял векторное умножение this-> diffs [i] * dIdx [i] и добавлял это к этому-> distro [i], но этот код выполнял 50 процентов помедленнее. Поэтому я думаю, что попал в стену.

Большое спасибо всем. D.

Answer 1

Это предложение для небольшой оптимизации, устраняющее необходимость в потолке, двух приведениях и одном из множителей. Если вы работаете на процессоре с фиксированной точкой, это объясняет, почему умножения и отливки между float и int занимают так много времени. В этом случае попробуйте использовать оптимизацию с фиксированной точкой или включить плавающую точку в своем компиляторе, если процессор ее поддерживает!

for (unsigned int idxSim = 0; idxSim < _g.xSimulationCount; idxSim++) 
{ 
    generatedVal = 0.0; 
    for (register unsigned int idxDay = 0; idxDay < 365; idxDay ++) 
    { 
     prob = (FLT_TYPE)fastrand();   // prob [0,1] 
     dIdx = prob * dMaxDistroIndex;  // scale prob to distro function size 
              // to get an index into distro array 
     iIdx1 = (long)dIdx; 
     _floor = (FLT_TYPE)iIdx1;  // fast version of floor 
     iIdx2 = iIdx1 + 1; 

     // interpolation per se 
     { 
      const FLT_TYPE diff = this->distro[iIdx2] - this->distro[iIdx1]; 
      const FLT_TYPE interp = this->distro[iIdx1] + diff * (dIdx - _floor); 
      generatedVal += interp; 
     } 
    } 
    this->yearlyCashflows[idxSim] = generatedVal ; 
} 

Answer 2

Я бы рекомендовал исправить fastrand. Код с плавающей точкой не самый быстрый в мире, но особенно медленным является переключение между плавающей точкой и целым кодом. Поскольку вам нужен целочисленный индекс, используйте целочисленную случайную функцию.

Может быть даже полезно предварительно сгенерировать все 365 случайных значений в цикле.Поскольку вам нужно только log2(dMaxDistroIndex) бит случайности за значение, вы можете уменьшить количество вызовов RNG.

Вы бы впоследствии выбрали случайное число между 0 и 1 для интерполяции.