从范围生成随机整数-Java 学习之路

133

我需要一个能在给定范围内生成随机整数的函数（包括边界值） . 我没有不合理的质量/随机性要求，我有四个要求：

我需要快速 . 我的项目需要产生数百万（有时甚至数千万）的随机数，而我当前的发电机功能已被证明是一个瓶颈 .
我需要它合理均匀（使用rand（）非常好） .
最小 - 最大范围可以是<0,1>到<-32727,32727> .
它必须是可播种的 .

我目前有以下C代码：

output = min + (rand() * (int)(max - min) / RAND_MAX)

问题是，它并不是真正统一的 - 只有当rand（）= RAND_MAX（对于Visual C它是1/32727）时才返回max . 这是小范围的主要问题，如<-1,1>，其中最后一个值几乎从不返回 .

所以我 grab 了笔和纸，并提出了以下公式（它 Build 在（int）（n 0.5）整数舍入技巧上）：

enter image description here

但它仍然没有给我统一的分配 . 对于值-1,0,0，重复运行10000个样本给出37：50：13的比率 .

你能建议更好的配方吗？（甚至整个伪随机数发生器功能）

12 回答

249
一个快，比你的好一点，但仍然没有适当的统一分布式解决方案
```
output = min + (rand() % static_cast<int>(max - min + 1))
```
除非范围的大小是2的幂，否则 this method produces biased non-uniform distributed numbers 无论 rand() 的质量如何 . 如需全面测试此方法的质量，请read this .
回复于 2024-04-27T10:57:11+08:00

最简单（也就是最好）的C（使用2011标准）答案是

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

无需重新发明轮子 . 无需担心偏见 . 无需担心使用时间作为随机种子 .

回复于 2024-04-27T10:57:11+08:00

11
如果您的编译器支持C 0x并且使用它是一个选项，那么新的标准 <random> 标头可能满足您的需求 . 它具有高质量 uniform_int_distribution ，可以接受最小和最大边界（包括你需要的），你可以选择各种随机数发生器插入该发行版 .

这是生成在[-57,365]中均匀分布的百万随机 int 的代码 . 我已经使用了新的std <chrono> 设施来计时，因为你提到性能是你的一个主要问题 .
```
#include <iostream>
#include <random>
#include <chrono>

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    Clock::time_point t0 = Clock::now();
    const int N = 10000000;
    typedef std::minstd_rand G;
    G g;
    typedef std::uniform_int_distribution<> D;
    D d(-57, 365);
    int c = 0;
    for (int i = 0; i < N; ++i) 
        c += d(g);
    Clock::time_point t1 = Clock::now();
    std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
    return c;
}
```
对我来说（2.8 GHz Intel Core i5）打印出：

2.10268e 07每秒随机数 .

您可以通过将int传递给其构造函数来为生成器设定种子：
```
G g(seed);
```
如果您后来发现 int 未涵盖您的发布所需的范围，可以通过更改 uniform_int_distribution 来解决此问题（例如更改为 long long ）：
```
typedef std::uniform_int_distribution<long long> D;
```
如果你后来发现 minstd_rand 不是一个足够高质量的发生器，那么它也可以很容易地被换掉 . 例如 . ：
```
typedef std::mt19937 G;  // Now using mersenne_twister_engine
```
对随机数生成器进行单独控制，随机分布可以非常自由 .

我还计算了（未显示）此分布的前4个"moments"（使用 minstd_rand ），并将它们与theoretical values进行比较，以尝试量化分布的质量：
```
min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001
```
（ x_ 前缀是指"expected"）
回复于 2024-04-27T10:57:11+08:00
-1
我们将问题分成两部分：
- 生成0到（max-min）范围内的随机数 n .
- 将min添加到该数字
第一部分显然是最难的 . 我们假设rand（）的返回值是完全一致的 . 使用modulo会为第一个 (RAND_MAX + 1) % (max-min+1) 数字添加偏差 . 因此，如果我们能够神奇地将 RAND_MAX 改为 RAND_MAX - (RAND_MAX + 1) % (max-min+1) ，就不会有任何偏见 .

事实证明，如果我们愿意允许伪非确定性进入算法的运行时间，我们就可以使用这种直觉 . 每当rand（）返回一个太大的数字时，我们只需要另一个随机数，直到我们得到一个足够小的数字 .

现在运行时间为geometrically distributed，预期值为 1/p ，其中 p 是第一次尝试获得足够小数字的概率 . 由于 RAND_MAX - (RAND_MAX + 1) % (max-min+1) 始终小于 (RAND_MAX + 1) / 2 ，因此我们知道 p > 1/2 ，因此对于任何范围，预期的迭代次数将始终小于2 . 使用这种技术，在标准CPU上应该可以在不到一秒的时间内生成数千万个随机数 .

编辑：

虽然上述技术上是正确的，但DSimon的答案在实践中可能更有用 . 你不应该自己实现这些东西 . 我已经看到很多拒绝采样的实现并且通常很难看出它是否正确 .
回复于 2024-04-27T10:57:11+08:00
89
Mersenne Twister怎么样？ boost实现非常易于使用，并且在许多实际应用程序中经过了充分测试 . 我自己在几个学术项目中使用它，如人工智能和进化算法 .

这是他们的例子，他们做了一个简单的功能来滚动六面模具：
```
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

boost::mt19937 gen;

int roll_die() {
    boost::uniform_int<> dist(1, 6);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}
```
哦，在这里's some more pimping of this generator just in case you aren' t确信你应该把它用在极其劣等的 rand() 上：

Mersenne Twister是Makoto Matsumoto和Takuji Nishimura发明的“随机数”发生器;他们的网站包括许多算法实现 . 从本质上讲，Mersenne Twister是一个非常大的线性反馈移位寄存器 . 该算法在19,937位种子上运行，存储在32位无符号整数的624元素阵列中 . 值2 ^ 19937-1是梅森素数;操纵种子的技术基于较旧的“扭曲”算法 - 因此称为“Mersenne Twister” . Mersenne Twister的一个吸引人的方面是它使用二进制运算 - 而不是耗时的乘法 - 来生成数字 . 该算法还具有很长的周期和良好的粒度 . 它对于非加密应用程序既快速又有效 .
回复于 2024-04-27T10:57:11+08:00
4
```
int RandU(int nMin, int nMax)
{
    return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1));
}
```
这是32768个整数到（nMax-nMin 1）整数的映射 . 如果（nMax-nMin 1）很小（如您的要求），映射将非常好 . 但是请注意，如果（nMax-nMin 1）很大，则映射将不起作用（例如 - 您无法以相同的概率将32768值映射到30000个值） . 如果需要这样的范围 - 您应该使用32位或64位随机源，而不是15位rand（），或忽略超出范围的rand（）结果 .
回复于 2024-04-27T10:57:11+08:00
3
这是一个在_1442984中生成数字的无偏见版本：
```
int r;
do {
  r = rand();
} while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low));
return r % (high + 1 - low) + low;
```
如果您的范围相当小，则没有理由在 do 循环中缓存比较的右侧 .
回复于 2024-04-27T10:57:11+08:00
13

我推荐Boost.Random library，它是非常详细和详细记录的，允许您明确指定您想要的分发，并且在非加密方案中实际上可以outperform一个典型的C库rand实现 .

回复于 2024-04-27T10:57:11+08:00
1
假设min和max是int值，[和]表示包含此值，（和）表示不包含此值，使用上面的方法使用c rand（）获取正确的值

reference：for（）[] define，访问：

https://en.wikipedia.org/wiki/Interval_(mathematics)

对于rand和srand函数或RAND_MAX定义，请访问：

http://en.cppreference.com/w/cpp/numeric/random/rand

[min，max]
```
int randNum = rand() % (max - min + 1) + min
```
（分钟，最大值]
```
int randNum = rand() % (max - min) + min + 1
```
[min，max）
```
int randNum = rand() % (max - min) + min
```
（分，最大）
```
int randNum = rand() % (max - min - 1) + min + 1
```
回复于 2024-04-27T10:57:11+08:00
0
在这个线程中已经讨论了拒绝采样，但我想基于 rand() % 2^something 没有引入任何偏差的事实提出一个优化，如上所述 .

算法非常简单：
- 计算大于间隔长度的2的最小功率
- 在"new"间隔中随机化一个数字
- 如果小于原始间隔的长度，则返回该数字
- 否则拒绝
这是我的示例代码：
```
int randInInterval(int min, int max) {
    int intervalLen = max - min + 1;
    //now calculate the smallest power of 2 that is >= than `intervalLen`
    int ceilingPowerOf2 = pow(2, ceil(log2(intervalLen)));

    int randomNumber = rand() % ceilingPowerOf2; //this is "as uniform as rand()"

    if (randomNumber < intervalLen)
        return min + randomNumber;      //ok!
    return randInInterval(min, max);    //reject sample and try again
}
```
这特别适用于小间隔，因为2的功率将“更接近”实际间隔长度，因此未命中的数量将更小 .

PS
显然避免递归会更有效率（不需要一遍又一遍地计算日志天花板......）但我认为这个例子更具可读性 .
回复于 2024-04-27T10:57:11+08:00

-2

这个公式非常简单，所以试试这个表达式，

int num = (int) rand() % (max - min) + min;  
 //Where rand() returns a random number between 0.0 and 1.0

回复于 2024-04-27T10:57:11+08:00

59
如果我没有弄错，以下表达式应该是公正的：
```
std::floor( ( max - min + 1.0 ) * rand() ) + min;
```
我在这里假设rand（）给你一个0.0到1.0范围内的随机值，不包括1.0，max和min是整数，条件是min <max .
回复于 2024-04-27T10:57:11+08:00

从范围生成随机整数

12 回答

相关问题