накопление Оптимизация векторов для Монте-Карло моделирования

Я хочу, чтобы оптимизировать следующий код:накопление Оптимизация векторов для Монте-Карло моделирования

Во время моделирования методом Монте-Карло я аккумулировать некоторые количества f(x) (f(x) стоит дорого вычислить) и сохранить их в массиве bins после каждой выборки шаг.

РЕДАКТИРОВАТЬ: Р (х) не является детерминированной функцией от х (я имею в виду он генерирует псевдо-случайных чисел и использует их, чтобы изменить результат), а также зависит от previoulsy расчетных значений F (Y)

for(int n=0;n<N;n++) 
{ 
    // compute some values f(x) at points "p" 
    for(auto k: p) bins[k] += f(k); 
}

p.size() намного меньше размера bins, но в конечном итоге большинство элементов будет установлено.

После моделирования я аккумулировать свои конечные значения, делая взвешенную сумму по bins (g является поиск в другом массиве):

for(int l=0;l<M;l++) 
    for(int k=0;k<bins.size();k++) 
     finalResult[l] += g(k,l)*bins[k];

Я мог бы, конечно, вычислить мой обновленный finalResult после каждого шага дискретизации, это однако замедляет работу программы, из-за цикла выше M.

Я уже пробовал очень простой boost::accumulate, но это не улучшило производительность (если я останусь с этим дизайном, мне придется использовать его в конечном итоге из-за стабильности, хотя).

Все массивы имеют тип Eigen::MatrixXd, так как мне нужны они для операций BLAS.

p.size() < 10^2 
N ~ 10^7 
M ~ 10^4 
bins.size() ~ 10^5

У вас есть какие-либо предложения, по которым методы могут быть полезны для оптимизации здесь?

источник

2016-12-05 Atom

метод вы используете внешний вид достаточно хорошо оптимизированы уже. Есть ли причина, почему вы ожидаете, что ее можно улучшить? Я бы вообще ожидал, что, полагая, что вы не делаете ничего глупого, как ненужное вычисление того же дорогостоящего значения два раза подряд, любые существенные улучшения должны были бы произойти от изменений высокого уровня к алгоритму моделирования Монте-Карло. –

алгоритм monte carlo уже сильно оптимизирован (имеется много матричных/векторных продуктов, которые не могут быть уменьшены). Профилирование его заявления показало, что это накопление занимает больше всего времени. так что я надеюсь, что я упустил некоторые менее очевидные оптимизации – Atom

Попробуйте вычислить f(x) только один раз для каждого из значений N (т. Е. Memoization). Так, например, если N велико (например, именно в этой ситуации), попробуйте изменить свой цикл, чтобы что-то вроде следующего:

static std::unordered_map<unsigned int, double> memoizedFunction; 
for(int n=0;n<N;n++) 
{ 
    // compute some values f(x) at points "p" 
    for(auto k: p) 
    { 
     auto it = memoizedFunction.find(k); 
     if (it == memoizedFunction.end()) 
     { 
      it = memoizedFunction.emplace(f(k)).first; 
     } 

     bins[k] += *it; 
    } 
}

В качестве альтернативы, вы можете просто сохранить количество раз k я бин БЫЛА hit в bins[k], а затем в конце пройдите и вычислите bins[k] * f(k) для каждого k.

источник

2016-12-05 16:40:48

лучше, чем найти/emplace, вставка/набор должен улучшить perf! – YSC

Это на самом деле очень хорошая идея, я уже думал об этом относительно g. f (x), однако, имеет случайную составляющую, поскольку она исходит из моделирования monte carlo (я действительно должен был сказать это в объяснении выше). это также означает, что f (k + 1) зависит от f (k) не очевидным образом. – Atom

Просто мысль здесь, но вы, если вы могли бы проверить, что Р (х) является линейным преобразование, то вы можете создать матрицу таким образом, что
[f(x)] = A[x] where [x] is the coordinates of x with respect to some basis B. 
Это может сделать п (х) проще и быстрее вычислять, особенно если x существует в векторном пространстве с малым базисом.

Однако, если преобразование между координатами и ответом является дорогостоящим , которое может повредить любые выгоды (просто имейте это в виду).

Вот некоторые ссылки, которые могли бы помочь объяснить матричное представление линейных преобразований .

https://math.colorado.edu/~nita/MatrixRepresentations.pdf https://math.dartmouth.edu/archive/m24w07/public_html/Lecture12.pdf https://en.wikipedia.org/wiki/Transformation_matrix

источник

2016-12-05 16:48:24

накопление Оптимизация векторов для Монте-Карло моделирования

ответ

Смежные вопросы