526互联

C++随机数random库 介绍及应用

发布时间 2023-11-29 23:13:39作者: 橙皮^-^

一、摘要

随机数可以应用在很多场景下如游戏抽卡、抽奖、场景生成、洗牌，歌曲app中的随机播放，社交app中的匹配等以及随机化算法。
以下是针对C中随机函数rand、C++random库使用的总结，以及一些随机应用例子

二、C/C++ 中的rand 函数

使用时需要引入头文件<stdlib.h>
该函数返回一个在[0, RAND_MAX]范围内的数字，RAND_MAX该宏定义值取决于实现，至少为32767
使用rand()需要一个随机种子，可以使用srand(seed)来设置随机种子(这里的seed一般选择当前系统时间time(0))，当程序没有调用srand，会默认使用srand(1)来作为随机种子

rand函数使用到的随机数生成算法--线性同余方法

\[N_{j+1} = (A \quad *\quad N_j + B) (mod \quad M) \]

可以看到当前的随机数，是根据上次随机数进行计算得到。因此同一程序使用相同的seed俩次运行，同一机器和编译器下，随机结果会是相同的。这样可以在程序应用中获得可再现的随机过程。
rand和srand伪代码实现，glibc rand源码实现

unsigned long _Randseed = 1; //默认随机种子为1

int rand(void) {
  _Randseed = _Randseed * 1103515245 + 12345;
  return ((unsigned int)(_Randseed >> 16) & RAND_MAX);
}

void srand(unsigned int seed) {
  _Randseed = seed;
}

需要注意的是rand函数不是线程安全的，多个线程同时调用rand可能获得同样的结果：多线程rand获得一样结果原因

使用比较简单

#include <cstdlib>
#include <iostream>

int main(int argc, char**argv)
{
  srand(time(nullptr));
  //如果在应用程序中需要一个可重复的随机过程
  //使用固定的seed作为srand参数
  std::cout << "randmax: " << RAND_MAX << std::endl;
  for(int i = 0; i < 10; i++)
  {
    std::cout << " " << rand();
  }
  std::cout << std::endl;
  return 0;
}

三、C++random库

random库主要由随机数引擎(Random number engines)和随机数分布(Random number distributions)组成，使用时需要引入头文件 #include <random>。
使用随机数引擎生成一定范围内随机数，使用随机分布可以得到满足一定规律的分布（均匀分布，伯努利分布、泊松分布、正太分布、抽样分布）的随机数

3.1 随机数引擎

3.1.1 模板类
模板 作用
linear_congruential_engine 实现线性同余算法 速度适中
mersenne_twister_engine 实现 Mersenne twister算法 速度较慢, 具有最长非重复序列
subtract_with_carry_engint 实现滞后斐波那契算法, 速度最快
3.1.2 非确定性随机数
  • std::random_device 是一个非确定性随机数生成器。通常被用作生成伪随机数器的种子。

3.1.3 一些预定义的随机数引擎

  • minstd_rand0 / minstd_rand（C++11）//线性同余法生成随机数
#include <iostream>
#include <random>
//std::minstd_rand0 
//定义：std：：linear_congruential_engine<std：：uint_fast32_t， 16807， 0， 2147483647>

int main(int argc, char**argv)
{

  std::random_device rd;
  unsigned int seed = rd();
  std::minstd_rand0 gen(seed);
  for(int i = 0; i < 10; i++)
  {
    std::cout << " " << gen();
  }
  return 0;
}
  • mt19937 (32位)/ mt19937_64 （64 位）使用Mersenne twister算法生成随机数，随机效果最好
#include <iostream>
#include <random>
//std::mt19937
/*定义
std::mersenne_twister_engine<std::uint_fast32_t、32、624、397、31、
0x9908b0df,11,
0xffffffff,7,
0x9d2c5680,15,
0xefc60000,18,1812433253>
*/
int main(int argc, char**argv)
{
  std::random_device rd;
  unsigned int seed = rd();
  std::mt19937 mt_r(seed);
  for(int i = 0; i < 10; i++)
  {
    std::cout << " " << mt_r();
  }
  return 0;
}
  • ranlux24_base/ranlux48_base 使用滞后斐波那契算法，与其他比较速度最快
#include <iostream>
#include <random>
//std::ranlux24_base
//std::subtract_with_carry_engine<std::uint_fast32_t, 24, 10, 24>
int main(int argc, char**argv)
{
	 std::random_device rd;
  unsigned int seed = rd();
  std::ranlux24_base r(seed);
  for(int i = 0; i < 10; i++)
  {
    std::cout << " " << r();
  }
  return 0;
}

3.2 随机数分布

3.2.1 均匀分布

在闭区间[a, b]中返回一个整数i，i的概率为

\[P(i|a,b) = \frac{1}{(b-a)+1} \]

使用方式

#include <iostream>
#include <random>
 
int main()
{
    std::random_device rd;//非确定性随机数生成器
    std::mt19937 gen(rd()); //使用Mersenne twister算法随机数生成器
    std::uniform_int_distribution<> distrib(1, 6); //随机均匀分布[1,6]区间
 
	//随机在闭区间[1,6]中返回一个数
    for (int n = 0; n != 10; ++n)
        std::cout << distrib(gen) << ' ';
    std::cout << '\n';
}

3.2.1 伯努利分布(0-1分布)

\[p(b/p)= \left\{\begin{matrix} p, if \quad b \quad is \quad true \\ 1-p, if \quad b \quad is \quad false \end{matrix}\right. \]

使用

#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
 
int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::bernoulli_distribution d(0.25); //默认参数为0.5，返回true的概率
 
    std::map<bool, int> hist;
    for (int n = 0; n < 10000; ++n)
        ++hist[d(gen)];
 
    std::cout << std::boolalpha;
    for (auto const& [key, value] : hist)
        std::cout << std::setw(5) << key << ' '
                  << std::string(value / 500, '*') << '\n';
}

还有泊松、正太、抽样方式随机分布，更多查看

四、随机数相关

4.1 洗牌算法 Knuth_Durstenfeld_Shuffle，就地洗牌

打乱一个数组num[n]， 从后向前遍历，当前位置i，从[0, i-1]中随机选择一个元素与num[i]交换

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Knuth_Durstenfeld_Shuffle 算法是通过交换原数组的元素来达到打乱效果，当不能修改原数组，需要返回洗牌后新数组，可以使用"inside-out" 算法

4.2 "inside-out" 洗牌算法，不修改原数组

从原数组source[n]返回打乱后数组a，从前往后遍历原数组，当前位置i，从[0,i-1]随机选值j，
当 \(j != i \quad a[i] =a[j]\) 然后将source[i]赋值给a[j]

To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based:
  for i from 0 to n − 1 do
      j ← random integer such that 0 ≤ j ≤ i
      if j ≠ i
          a[i] ← a[j]
      a[j] ← source[i]

4.3 线段分割（红包随机、固定长度随机切割）

  • 例子：生成 10 个随机数 （0, 100） 且最终 10 个随机数之和为 100（或者固定100面值随机10个红包）
    线段分割：在一根1到100的数轴上，选取9个点，拿到10个线段，计算每个线段的长度
    C++代码实现
#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <set>

int main(int argc, char *argv[])
{
  std::random_device device;
  std::mt19937 mt(device());
  std::uniform_int_distribution<> dis(1, 100);
  std::set<int> random_val;
  //需要进行去重，防止有重复的点。
  while(random_val.size() < 9)
  {
    random_val.insert(dis(mt));
  }
  random_val.insert(0);
  random_val.insert(100);
  auto last = random_val.begin();
  std::vector<int> ret;
  for(auto cur = std::next(last); cur != random_val.end(); ++cur)
  {
    ret.push_back((*cur) - (*last));
    last = cur;
  }
  int total = 0;
  for(auto num : ret)
  {
    std::cout << " " << num;
    total += num;
  }
  std::cout << std::endl;
  std::cout << "totalnum: " << total << std::endl;
  return 0;
}
//结果输出
// 24 11 38 2 1 1 4 8 2 9
//totalnum: 100

4.4 二倍均值法（提到红包随机，网上还提及这个算法）

每次在区间\([0.01,M/N*2-0.01]\)随机选取一个数，M是剩余红包金额，N红包剩余数量。

六、参考