10

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

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

目前我正在使用 George Marsaglia 的 Multiply With Carry 算法，它在 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 个值，但它似乎是一种确保没有冲突的优化方式。这会提供良好的随机输出吗？它相当快。

4

2 回答 2

5

如果你只使用随机数组中的前 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);
}
于 2009-08-07T21:52:59.670 回答
4

罗斯模拟书建议如下：


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

于 2009-08-07T21:54:09.883 回答