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

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

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

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

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

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

Update:

Спасибо за ответы. У меня есть еще один вопрос относительно метода, который я только что придумал после моего сообщения. Вопрос в том, обеспечит ли это надежный (при условии, что RNG хороший) случайный выход. В основном мой метод состоит в том, чтобы установить массив целых значений той же длины, что и мой входной массив, установить каждое значение равным нулю. Теперь я начинаю случайным образом выбирать 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 значений наугад, за исключением того, что это кажется несколько оптимизированным способом обеспечения отсутствия столкновений. Будет ли это обеспечивать хороший случайный выход? Его довольно быстро.

Ответы

Ответ 1

Если вы используете только первые 20 значений в рандомизированном массиве, вам нужно всего лишь выполнить 20 шагов алгоритма Fisher-Yates (версия Knuth). Тогда 20 значений были рандомизированы (фактически в конце массива, а не в начале, в обычной формулировке), в том смысле, что оставшиеся 80 шагов алгоритма гарантированно не перемещают их. Остальные 80 позиций не полностью перетасованы, но кто заботится?

Код С++ (итераторы должны быть произвольными):

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

Ответ 2

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


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