c++ 随机数问题的相关研究

时间:2022-11-14 14:36:36

1、问题背景

某项目中有个复杂的排序,先是各种规则依次排序,最后如果依然并列的话,那就随机位置,名次并列。测试中发现一个诡异现象,并列时随机排序但随机后2个case打印的顺序每次都一样,随机数没有起到任何作用。经过分析发现,随机数种子srand(clock()),本意是希望连续调用这个函数,给多个随机数设置种子,实际上设置的种子相同,最后产生的随机数是伪随机数。那么有没有一种随机数方法可以在较快的循环中,保证随机性呢?

原问题较复杂,给个类似的例子说明具体场景:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void test_random()
{
 vector<int> vec;
 vec.resize(100);
 iota(vec.begin(), vec.end(), 1);
 vector<int> vec2(vec);
 
 srand(clock());
 random_shuffle(vec.begin(), vec.end());
 srand(clock());
 random_shuffle(vec2.begin(), vec2.end());
 int cnt = 0;
 cout << "vec:" << endl;
 for (auto v : vec) {
  cout << v << " ";
  if ((++cnt % 10) == 0) cout << endl;
 }
 cout << endl<< endl;
 cnt = 0;
 cout << "vec2:" << endl;
 for (auto v : vec2) {
  cout << v << " ";
  if ((++cnt % 10) == 0) cout << endl;
 }
}

输出结果为:

c++ 随机数问题的相关研究

2、rand()和srand()

rand()和srand()是c函数,在stdlib.h中定义,rand()能产生0--32767范围的随机数。

如果只使用rand,则每次输出的随机数都是一样的,相当于使用srand(1)作为默认种了。如果给定种了,则能产生不同的随机数,所以time或clock函数就是一个好种子,获取计算机的时间,用秒或毫秒来做随机数种子以产生不同的随机数。但是在某些场景下,会引发下列问题:

问题1:在程序运行较慢或不需要连续产生随机数时,用时钟当做种子没有问题,但要快速产生不同的组数的随机数时,就会出现前面出现的现象,较大概率出现相同的随机数。

问题2:如果希望生成某个范围的随机数,则不好控制,通常会采用取模的方式,而这种方式会破坏随机数的分布概率。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
// 0--10 的随机数
srand((unsigned int)time(NULL));
int r = rand() % 10
// 100--200的随机数
int min = 100;
int max = 200;
srand((unsigned int)time(NULL));
int r = rand() % (max - min) + min
 
// [0--1.0] 浮点数
srand((unsigned int)time(NULL));
float r = rand() % RAND_MAX

3、c++11 随机数

c++11引入了random头文件,可以更加精确的产生随机数,并且提供了完善的操作接口。C++标准规定了随机数设施,包括均匀随机位生成器(Uniform random bit generators,URBG)和随机数分布等,定义在<random>中。

参考文档:http://www.cplusplus.com/reference/random/?kw=random

This library allows to produce random numbers using combinations of generators and distributions:

Generators: Objects that generate uniformly distributed numbers.

Distributions: Objects that transform sequences of numbers generated by a generator into sequences of numbers that follow a specific random variable distribution, such as uniform, Normal or Binomial.

random标准款主要包括:

生成器:生成均匀分布伪随机数的对象

分布:将生成器生成的数序列转换为某种特定数学概率分布的序列,如均匀分布、正态分布、泊松分布等。

3.1、生成器

1)random_device生成器

C++11提供了一个random_device随机数类,英文叫“Non-deterministic random number generator”,这是一个非确定性随机数生成器,它并不是由某一个数学算法得到的随机序列,而是通过读取文件,读什么文件看具体的实现(Linux可以通过读取/dev/random文件来获取)。文件的内容是随机的,简单理解即这个类依靠系统的噪声产生随机数。

2)伪随机数引擎

伪随机数引擎,实现方式属于模板类,是使用算法根据初始种子生成伪随机数的生成器。

?
1
2
3
linear_congruential_engine:线性同余生成引擎,是最常用也是速度最快的,但随机效果一般
mersenne_twister_engine:梅森旋转算法,随机效果最好。
subtract_with_carry_engine:滞后Fibonacci算法。

随机数引擎需要一个 整型参数作为种子,对于给定的单个或多个种子,随机数生成器总会生成相同的序列,这在测试时非常有用。当测试完成,则需要随机的种子以产出不同的随机数,推荐使用random_device作为随机数种子。

3.2、适配器

除了生成器模板库外,c++11还设计了几种适配器。

discard_block_engine: Discard-block random number engine adaptor (class template ) independent_bits_engine: Independent-bits random number engine adaptor (class template ) shuffle_order_engine :Shuffle-order random number engine adaptor (class template )

3.3、随机分布模板类

随机数引擎产生的随机数值都比较大,使用时经常需要限定到一个范围内,c++11提供了符合各种概率分布的随机数生成模板类,比如:均匀分布,正态分布,泊松分布等。

c++ 随机数问题的相关研究

以均匀分布为例:

?
1
2
template< class IntType = int > class uniform_int_distribution;
template< class RealType = double > class uniform_real_distribution;

测试1:直接使用引擎产生随机数,范围很大。

?
1
2
3
4
5
6
7
8
9
10
11
12
random_device rd;
mt19937 g(rd());
for (int n = 0; n < 10; ++n)
{
 cout << g() << " ";
}
/* 输出
case 1:
649838310 2697128147 116396177 1728659882 2608399735 1196122003 1824385544 3670102805 2610106284 1577110367
case 2:
2220490604 2877041131 4118289859 1423499548 3901014967 230558428 3106974485 2887363336 1389836600 4020707730
*/

测试2:使用均匀分布类模板产生随机数,可以限定生成的随机数的范围。

?
1
2
3
4
5
6
7
8
9
10
11
12
random_device rd;
mt19937 g(rd());
uniform_int_distribution<> dis(1, 100);
for (int n = 0; n < 10; ++n)
{
 cout << dis(g) << " ";
}
/* 输出
case 1: 67 23 61 3 91 88 81 61 57 60
case 2: 51 1 29 75 81 32 8 8 47 5
cae 3: 92 1 22 24 84 20 72 27 66 39
*/

3.4、用法总结

1、定义种子,可以是随机种子或者固定种子,固定种子方便测试用,但每次产生的随机数都一致。

2、选择随机引擎,把种子值传入当做参数。

3、选择合适分布方式,创建随机分布对象,可以在此时指定需要的随机数的范围。

4、把引擎传入随机数分布模板类对象,输出随机数。

4、问题解决

c++ 提供了一个shuffle函数,相比于random_shuffle,shuffle可以指定随机数引擎,如果指定一个非确定性引擎,则能保证连续生成的两组随机数各不相同,达到设计效果。

?
1
2
template <class _RanIt, class _Urng>
void shuffle(_RanIt _First, _RanIt _Last, _Urng&& _Func)

修改后的测试函数:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void test_random()
{
 vector<int> vec;
 vec.resize(100);
 iota(vec.begin(), vec.end(), 1);
 vector<int> vec2(vec);
 
 auto engine = std::default_random_engine(std::random_device()());
 shuffle(vec.begin(), vec.end(), engine);
 shuffle(vec2.begin(), vec2.end(), engine);
  
 int cnt = 0;
 cout << "vec:" << endl;
 for (auto v : vec) {
  cout << v << " ";
  if ((++cnt % 10) == 0) cout << endl;
 }
 cout << endl<< endl;
 cnt = 0;
 cout << "vec2:" << endl;
 for (auto v : vec2) {
  cout << v << " ";
  if ((++cnt % 10) == 0) cout << endl;
 }
}

上面例子using default_random_engine = mt19937; 其中,mt19937是一个引擎,最大值为0Xffffffff。

using mt19937 = mersenne_twister_engine<unsigned int, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7, 0x9d2c5680, 15,  0xefc60000, 18, 1812433253>;

输出结果为:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vec:
85 7 58 8 29 17 60 57 81 71
82 93 4 47 84 40 65 79 37 24
3 14 36 25 32 16 91 48 86 38
63 78 80 28 44 39 34 90 69 13
74 1 77 59 88 41 46 56 33 62
21 18 30 52 89 22 87 27 9 53
70 51 2 72 92 42 26 66 73 97
15 43 31 49 100 68 54 35 12 99
6 67 5 96 94 83 10 45 61 50
23 76 19 98 11 55 75 20 95 64
 
vec2:
37 51 12 62 99 95 65 1 78 29
80 13 48 72 83 23 25 75 97 68
86 40 24 30 84 4 47 28 76 57
33 38 16 18 69 9 70 31 42 49
52 71 91 96 81 73 34 45 10 26
2 93 89 41 54 64 44 22 36 39
87 43 63 55 3 32 27 19 85 79
35 5 58 11 56 59 21 88 15 100
74 53 8 14 60 92 17 50 7 90
6 20 67 77 98 61 66 82 46 94

c++随机数问题研究

原创首发:https://www.cnblogs.com/pingwen/p/14496607.html

以上就是c++ 随机数问题的相关研究的详细内容,更多关于c++随机数问题研究的资料请关注服务器之家其它相关文章!