Быстрая генерация случайного набора, моделирование методом Монте-Карло

У меня есть набор чисел ~ 100, я хочу выполнить симуляцию MC на этом наборе, основная идея состоит в том, что я полностью рандомизирую набор, провожу сравнение / проверку первых ~ 20 значений, сохраняю результат и повторяю.

Теперь фактический алгоритм сравнения / проверки чрезвычайно быстр, он фактически завершается примерно за 50 циклов ЦП. Имея это в виду и чтобы оптимизировать эти симуляции, мне нужно как можно быстрее сгенерировать случайные наборы.

В настоящее время я использую алгоритм Multiply With Carry Джорджа Марсальи, который довольно быстро предоставляет мне случайное целое число за 17 циклов процессора. Однако, используя алгоритм перетасовки Фишера-Йейтса, мне нужно сгенерировать 100 случайных целых чисел, ~ 1700 циклов ЦП. Это намного затмевает мое время сравнения.

Итак, мой вопрос: есть ли другие хорошо известные / надежные методы для выполнения этого типа моделирования MC, где я могу избежать длительного времени генерации случайного набора?

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

Обновление:

Спасибо за ответы. У меня есть еще один вопрос относительно метода, который я только что придумал после своего поста. Вопрос в том, обеспечит ли это надежный действительно (при хорошем ГСЧ) случайный вывод. В основном мой метод состоит в том, чтобы создать массив целочисленных значений той же длины, что и мой входной массив, установить каждое значение в ноль. Теперь я начинаю случайным образом выбирать 20 значений из входного набора следующим образом:

int pcfast[100];
memset(pcfast,0,sizeof(int)*100);
int nchosen = 0;
while (nchosen<20)
{
    int k = rand(100); //[0,100]
    if ( pcfast[k] == 0 )
    {
        pcfast[k] = 1;
        r[nchosen++] = s[k]; // r is the length 20 output, s the input set.
    }
}

В основном то, что я упомянул выше, случайный выбор 20 значений, за исключением того, что это кажется несколько оптимизированным способом обеспечения отсутствия коллизий. Обеспечит ли это хороший случайный вывод? Это довольно быстро.


c++ random montecarlo
person DeusAduro    schedule 07.08.2009    source источник
comment
В ответ на обновление: да, мне кажется, это справедливо.   -  person Steve Jessop    schedule 08.08.2009
comment
Если вы можете найти хороший генератор MWC с модулем 100, он более или менее эквивалентен использованию F-Y с rnd, реализованным как int rand(int n) { int r; do { r = rand100() } while (r >= n); return r}. Но он выполняет немного меньше копирования, и на x64 у вас может быть даже достаточно регистров, чтобы хранить эти 100 флагов в двух длинных переменных и не перетекать в стек.   -  person Steve Jessop    schedule 08.08.2009
comment
Таким образом, все сводится к тому, выбирать ли 0-99 и отбрасывать, если выход за пределы диапазона приводит к гораздо большему перехвату случайных чисел, чем любой другой метод принуждения вашего существующего генератора MWC к требуемому диапазону (например, с использованием генератора с широким диапазоном и только отбрасывая меньшую часть значений).   -  person Steve Jessop    schedule 08.08.2009
comment
На самом деле я взял проверенную реализацию MWC с хорошими свойствами и встроил ее для непосредственного выполнения модуля. Это довольно приятно, потому что я на самом деле избегаю использования оператора "%", который работает довольно медленно.   -  person DeusAduro    schedule 08.08.2009
comment
Кроме того, на основе пробного создания 10 миллионов наборов образцов частичный F-Y оказался быстрее, чем предложенный мной метод, поэтому я буду придерживаться его.   -  person DeusAduro    schedule 08.08.2009

Ответы (2)


arrow_upward
5
arrow_downward

Если вы используете только первые 20 значений в рандомизированном массиве, вам нужно выполнить только 20 шагов алгоритма Фишера-Йейтса (версия Кнута). Затем 20 значений были рандомизированы (фактически, в конце массива, а не в начале, в обычной формулировке) в том смысле, что оставшиеся 80 шагов алгоритма гарантированно не переместят их. Остальные 80 позиций перемешаны не полностью, но кого это волнует?

Код C ++ (итераторы должны иметь произвольный доступ):

using std::swap;

template <typename Iterator, typename Rand> // you didn't specify the type
void partial_shuffle(Iterator first, Iterator middle, Iterator last, Rand rnd) {
    size_t n = last - first;
    while (first != middle) {
        size_t k = rnd(n);   // random integer from 0 to n-1
        swap(*(first+k),*first);
        --n;
        ++first;
    }
}

При возврате значения от first до middle-1 перетасовываются. Используйте это так:

int arr[100];
for (int i = 0; i < 100; ++i) arr[i] = i;
while (need_more_samples()) {
    partial_shuffle(arr, arr+20, arr+100, my_prng);
    process_sample(arr, arr+20);
}
person Steve Jessop    schedule 07.08.2009
comment
Работает очень хорошо, как и ожидалось, сэкономило 80% времени генерации. - person DeusAduro; 08.08.2009

arrow_upward
4
arrow_downward

Книга по симуляции Росс предлагает примерно следующее:


double return[10];
for(int i=0, n=100; i < 10; i++) {
  int x = rand(n);  //pseudocode - generate an integer on [0,n]
  return[i] = arr[x];
  arr[x] = arr[n];
  n--;
}

person Community    schedule 07.08.2009
comment
На вики-страницу Fisher-Yates есть ссылка на него как на современный алгоритм: en.wikipedia.org/wiki/ - person klochner; 08.08.2009
comment
Обратите внимание, что при желании это также можно сделать на месте, поменяв местами значения вместо копирования на вывод и копирования внутри массива. Это оставляет 100 значений готовыми для повторной перетасовки, тогда как эта версия уничтожает входной массив. Повторная настройка ввода может иметь большое значение по сравнению с ослепляющими скоростями, о которых говорит OP. Результатом внесения этого изменения является мой ответ :-) - person Steve Jessop; 08.08.2009
comment
договорились о том, что на месте будет быстрее. - person klochner; 08.08.2009
comment
В самом деле, я собираюсь попробовать по отдельности, забавно, что я потратил так много времени на оптимизацию кода сравнения, LUT, идеальных минимальных хэшей и тому подобного ... потом я перешел к рандомизации, ааа. - person DeusAduro; 08.08.2009