快速生成随机集，蒙特卡洛模拟 [英] Fast generation of random set, Monte Carlo Simulation

问题描述

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

I have a set of numbers ~100, I wish to perform MC simulation on this set, the basic idea is I fully randomize the set, do some comparison/checks on the first ~20 values, store the result and repeat.

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

Now the actual comparison/check algorithm is extremely fast it actually completes in about 50 CPU cycles. With this in mind, and in order to optimize these simulations I need to generate the random sets as fast as possible.

当前，我使用的是George Marsaglia的乘数乘以算法，该算法在17个CPU周期中为我提供了一个随机整数，相当快.但是，使用Fisher-Yates混排算法，我必须生成100个随机整数，约1700个CPU周期.这大大使我的比较时间蒙上了阴影.

Currently I'm using a Multiply With Carry algorithm by George Marsaglia which provides me with a random integer in 17 CPU cycles, quite fast. However, using the Fisher-Yates shuffling algorithm I have to generate 100 random integers, ~1700 CPU cycles. This overshadows my comparison time by a long ways.

所以我的问题是，还有其他众所周知/健壮的技术可以进行这种类型的MC仿真吗?在这种情况下，我可以避免较长的随机集生成时间?

So my question is are there other well known/robust techniques for doing this type of MC simulation, where I can avoid the long random set generation time?

我考虑从集合中随机选择20个值，但是我将不得不进行碰撞检查以确保选择了20个唯一条目.

I thought about just randomly choosing 20 values from the set, but I would then have to do collision checks to ensure that 20 unique entries were chosen.

更新:

感谢您的回复.关于发布后刚想出的方法，我还有另一个问题.问题是，这是否会提供可靠的(假设RNG很好)随机输出.基本上，我的方法是建立一个与输入数组长度相同的整数值数组，并将每个值都设置为零.现在，我开始从输入集中随机选择20个值，如下所示:

Thanks for the responses. I have another question with regards to a method I just came up with after my post. The question is, will this provide a robust truly (assuming the RNG is good) random output. Basically my method is to set up an array of integer values the same length as my input array, set every value to zero. Now I begin randomly choosing 20 values from the input set like so:

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个值，除了它看起来是一种确保没有冲突的优化方法.这会提供良好的随机输出吗?它相当快.

Basically what I mentioned above, choosing 20 values at random, except it seems like a somewhat optimized way of ensuring no collisions. Will this provide good random output? Its quite fast.

推荐答案

如果仅使用随机数组中的前20个值，则只需要执行Fisher-Yates算法(Knuth版本)的20个步骤.然后，在保证算法的其余80个步骤不会移动它们的意义上，已经对20个值进行了随机化(实际上是在数组的末尾而不是在通常的表示形式中，在开始时是随机的).其他80个职位并未全部改组，但谁在乎呢?

If you only use the first 20 values in the randomised array, then you only need to do 20 steps of the Fisher-Yates algorithm (Knuth's version). Then 20 values have been randomised (actually at the end of the array rather than at the beginning, in the usual formulation), in the sense that the remaining 80 steps of the algorithm are guaranteed not to move them. The other 80 positions aren't fully shuffled, but who cares?

C ++代码(迭代器应该是随机访问的):

C++ code (iterators should be random-access):

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的值混洗.像这样使用它:

On return, the values from first through to middle-1 are shuffled. Use it like this:

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

这篇关于快速生成随机集，蒙特卡洛模拟的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！