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

Question

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

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

В настоящее время я использую алгоритм Multiply With Carry от George Marsaglia, который дает мне случайное целое число в 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 значений случайным образом, за исключением того, что это выглядит как несколько оптимизированный способ предотвращения коллизий. Это обеспечит хороший случайный вывод? Это довольно быстро.

Answer 1

Если вы используете только первые 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);
}

Answer 2

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

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