快速生成随机集，蒙特卡罗模拟

Question

我有一组大约 100 个数字，我希望对这组数字执行 MC 模拟，基本思想是我完全随机化该组，对前大约 20 个值进行一些比较/检查，存储结果并重复。

现在，实际的比较/检查算法非常快，它实际上在大约 50 个 CPU 周期内完成。 考虑到这一点，为了优化这些模拟，我需要尽快生成随机集。

目前，我正在使用 George Marsaglia 的乘法进位算法，该算法在 17 个 CPU 周期内为我提供了一个随机整数，速度相当快。 然而，使用 Fisher-Yates 洗牌算法，我必须生成 100 个随机整数，约 1700 个 CPU 周期。 这大大掩盖了我的比较时间。

所以我的问题是是否有其他众所周知/强大的技术来进行这种类型的 MC 模拟，我可以避免较长的随机集生成时间？

我考虑过从集合中随机选择 20 个值，但随后我必须进行冲突检查以确保选择 20 个唯一的条目。

更新：

感谢您的回复。 我还有一个关于我在发帖后刚刚提出的方法的问题。 问题是，这是否会提供一个真正可靠的（假设 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 个值，只不过这似乎是一种确保不发生碰撞的优化方法。 这会提供良好的随机输出吗？ 它的速度相当快。

Answer 1

如果您只使用随机数组中的前 20 个值，那么您只需执行 Fisher-Yates 算法（Knuth 版本）的 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

罗斯模拟书提出了如下建议：

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