在这个StackOverflow问题中:
所接受的答案表明,在给定的min
和max
之间生成随机整数的公式如下,其中包括min
和max
:
output = min + (rand() % (int)(max - min + 1))
但它也说
这还是有点偏低的数字..。它也有可能扩大它,以便它消除偏见。
但这并不能解释为什么它偏向较低的数字,或如何消除偏见。因此,问题是:这是在(有符号)范围内生成随机整数的最优方法,而不依赖于任何花哨的rand()
函数,如果是最优的话,如何消除偏差?
编辑:
我刚刚测试了@ while
-loop提出的浮点外推算法:
static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0);
return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax);
为了看有多少均匀的“球”正在“落入”并分布在许多“桶”中,一种是浮点外推的测试,另一种是while
-loop算法的测试。但是结果却是不同的,取决于“球”(和“桶”)的数量,所以我很难轻易地选出一个获胜者。工作代码可以在这一页找到。例如,对于10个桶和100个球,浮点外推法与理想概率的最大偏差小于while
-loop算法(分别为0.04和0.05 ),而对于1000个球,while
-loop算法的最大偏差较小(0.024和0.011),而对于10000个球,浮点外推法又做得更好(0.0034和0.0053),等等,没有很大的一致性。考虑到没有一种算法能够一致地产生比其他算法更好的均匀分布,这让我倾向于浮点外推,因为它的执行速度似乎比while
-loop算法快。那么,选择浮点外推算法好吗?还是我的测试/结论不完全正确?
发布于 2012-08-01 12:06:48
当随机数生成器(RAND_MAX+1)的输出数不能被期望的范围(max-min+1)均匀整除时,就会出现这个问题。由于将有一个从随机数到输出的一致映射,一些输出将被映射到更多的随机数。这是不管如何完成映射-你可以使用模块,除法,转换为浮点,无论你想出什么伏都教,基本的问题仍然存在。
问题的严重性很小,不需要严格要求的应用程序通常可以忽略它。范围越小,RAND_MAX越大,效果就越不明显。
我以你的例子程序为例,对它做了一些调整。首先,我创建了一个只有0-255范围的特殊版本的rand
,以更好地演示效果。我对rangeRandomAlg2
做了一些调整。最后,我将“球”的数量改为1000000,以提高一致性。您可以在这里看到结果:http://ideone.com/4P4HY
请注意,浮点版本产生两个紧密分组的概率,接近0.101或0.097,两者之间没有任何差别。这就是行动上的偏见。
我认为把这个叫做“Java的算法”有点误导--我相信它比Java要古老得多。
int rangeRandomAlg2 (int min, int max)
{
int n = max - min + 1;
int remainder = RAND_MAX % n;
int x;
do
{
x = rand();
} while (x >= RAND_MAX - remainder);
return min + x % n;
}
发布于 2012-08-01 04:08:52
问题是你在做模块操作。如果RAND_MAX
可以被模整除,这是没有问题的,但通常不是这样的。作为一个非常精心设计的例子,假设RAND_MAX
为11,模数为3。您将得到以下可能的随机数和下面的剩余数:
0 1 2 3 4 5 6 7 8 9 10
0 1 2 0 1 2 0 1 2 0 1
正如你所看到的,0和1的概率略高于2。
解决这一问题的一个选择是拒绝抽样:通过不允许上面的数字9和10,您可以使结果的分布再次均匀。最棘手的部分是弄清楚如何有效地做到这一点。在Java的java.util.Random.nextInt(int)
方法中可以找到一个非常好的例子(一个花了我两天时间来理解它为什么工作的例子)。
Java的算法有点棘手的原因是它们避免了像乘法和除法这样的缓慢操作。如果你不在乎的话,你也可以用幼稚的方式去做:
int n = (int)(max - min + 1);
int remainder = RAND_MAX % n;
int x, output;
do {
x = rand();
output = x % n;
} while (x >= RAND_MAX - remainder);
return min + output;
编辑:在上面的代码中纠正了一个fencepost错误,现在它可以正常工作了。我还创建了一个小示例程序(C#;对0到15之间的数字采用统一的PRNG,并通过各种方式为0到6之间的数字构造PRNG ):
using System;
class Rand {
static Random r = new Random();
static int Rand16() {
return r.Next(16);
}
static int Rand7Naive() {
return Rand16() % 7;
}
static int Rand7Float() {
return (int)(Rand16() / 16.0 * 7);
}
// corrected
static int Rand7RejectionNaive() {
int n = 7, remainder = 16 % n, x, output;
do {
x = Rand16();
output = x % n;
} while (x >= 16 - remainder);
return output;
}
// adapted to fit the constraints of this example
static int Rand7RejectionJava() {
int n = 7, x, output;
do {
x = Rand16();
output = x % n;
} while (x - output + 6 > 15);
return output;
}
static void Test(Func<int> rand, string name) {
var buckets = new int[7];
for (int i = 0; i < 10000000; i++) buckets[rand()]++;
Console.WriteLine(name);
for (int i = 0; i < 7; i++) Console.WriteLine("{0}\t{1}", i, buckets[i]);
}
static void Main() {
Test(Rand7Naive, "Rand7Naive");
Test(Rand7Float, "Rand7Float");
Test(Rand7RejectionNaive, "Rand7RejectionNaive");
}
}
结果如下(粘贴到Excel中并添加了单元格的条件着色,以使差异更加明显):
现在我修正了上述拒绝抽样中的错误,它的工作原理(在它偏置0之前)。正如您所看到的,浮点方法一点也不完美,它只是以不同的方式分配有偏数。
发布于 2012-08-01 04:12:37
很容易理解为什么这个算法会产生一个有偏差的样本。假设您的rand()
函数从集合{0, 1, 2, 3, 4}
返回一致整数。如果我想用它生成一个随机位0
或1
,我可以说是rand() % 2
。set {0, 2, 4}
给了我0
,而set {1, 3}
给了我1
--所以很明显,我用60%的可能性来采样0
,用40%的可能性来采样1
,一点也不一致!
要解决这个问题,您必须确保所需的范围除以随机数生成器的范围,或者在随机数生成器返回大于目标范围最大倍数的数字时丢弃结果。
在上面的例子中,目标范围为2,符合随机生成范围的最大倍数为4,因此我们丢弃任何不在集合{0, 1, 2, 3}
中的样本并再次滚动。
https://stackoverflow.com/questions/11758809
复制