C++中的随机数

发表于 更新于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟

使用C的随机数

实现

C中随机数函数非常简单，定义在<stdlib.h>中：

  • void srand(unsigned seed);

    1
    2
    3
    4
    5

      将随机种子设为`seed` ；**相同的种子将获得相同的随机数序列**，只要在程序开始初始化即可。

    - ```c
      int rand();
    

返回[0,RAND_MAX]之间的**伪随机数**。

初始化种子

一般使用<time.h>中的time()函数

1
time_t time(time_t* arg);

返回当前的日历时间，如果arg不为空，同时赋给arg。

1
2
srand(time(NULL));
srand(time(0));
1
srand(time(nullptr));

关于NULL,0,nullptr：在C中推荐使用NULL表示空指针，在C++中推荐使用0，在C++11中使用nullptr更好；在time()中可以任意使用。

问题

时间问题

  • 在Windows下，通常time()更新为每秒一次
  • 在Linux下，通常time()更新为每毫秒一次

当使用Windows对拍时，问题很严重：数据每秒才更新一次。当程序计算很快时，很多组数据无效。

范围问题

  • 在Windows下，通常RAND_MAX为32767($2^{15}-1$)
  • 在Linux下，通常RAND_MAX等于INT_MAX

演示代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//this code should be compiled <since> C++14
#include<bits/stdc++.h>
using namespace std;
int main()
{
	while(clock()<10*CLOCKS_PER_SEC)
	{
		srand(time(NULL));
		cout<<"\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b                                                            \b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b";
		for(int i=1;i<=10;i++)
			cout<<rand()<<' ';
		this_thread::sleep_for(100ms);
	}
	return 0;
}

编译说明：编译器必须至少支持C++14！ 若不支持C++11/14，使用sleep()代替this_thread::sleep_for(100ms)

该代码将运行大约10秒，展示随机数的更新情况以及随机数的范围。

在Windows下解决时间问题

高精度计时器

实现

在Windows下提供了一种高精度计时器，使用QueryPerformanceCounter和QueryPerformanceFrequency。

高精度计时器一个周期通常小于1微秒，该API最低系统要求为Windows 2000。

1
2
3
BOOL WINAPI QueryPerformanceCounter(
  _Out_ LARGE_INTEGER *lpPerformanceCount
);

获取当前的高精度计时器计数，成功则返回非0值。

1
2
3
BOOL WINAPI QueryPerformanceFrequency(
  _Out_ LARGE_INTEGER *lpFrequency
);

获取高精度计时器的频率。

其中LARGE_INTEGER定义为

1
2
3
4
5
6
7
8
9
10
11
typedef union _LARGE_INTEGER {
  struct {
    DWORD LowPart;
    LONG  HighPart;
  };
  struct {
    DWORD LowPart;
    LONG  HighPart;
  } u;
  LONGLONG QuadPart;
} LARGE_INTEGER, *PLARGE_INTEGER;

使用方法

1
2
3
LARGE_INTEGER t;
QueryPerformanceCounter(&t);
srand(t.LowPart);

毫秒计时器（备选）

实现

除了高精度计时器外，Windows还提供一个与clock()类似的函数GetTickCount。

1
DWORD WINAPI GetTickCount(void);

获取从系统启动开始经过的毫秒数，最高可达49.7天。

也就是说当系统连续运行49.7天后会从UINT_MAX降到0

什么，不可能连续运行49.7天？如果你启用快速启动(Windows 8+)，且不重新启动，系统实际上会在关机后继续"运行"。打开任务管理器-性能-CPU可以看到运行时间，轻松创造运行几天的纪录。

问题

虽然该函数返回值精确到毫秒，但实际上该计时器一般10~16毫秒更新一次。在程序运行非常快时，仍然会产生相同的数据；不过这种情况较为少见。

使用方法

1
srand(GetTickCount());

在Windows下解决范围问题

简单方法

如果要产生32位伪随机数，可以使用

1
2
3
4
int rand32()
{
	return (rand()<<16)+rand();
}

问题

  • 得到的取值范围不均匀，如rand32()&(1<<15)总是为0

  • 需要生成范围需要手工计算，设生成区间$[l,r]$之间的伪随机数

    1
    int r=rand()%(r-l+1)+l;

  • 由于需要多次计算会影响效率

使用C++11的伪随机数

C++11在CCF提供的环境下能基本使用，但不能以源代码提交

实现

C++11的随机数定义在<random>中，主要有2个概念

  • 随机数引擎
    • default_random_engine：默认随机数引擎
    • random_device：随机数设备，类似于rand()
  • 随机数范围
    • uniform_int_distribution：均匀分布的整数范围
    • uniform_real_distribution：均匀分布的实数范围
    • bernoulli_distribution：按概率生成的布尔型

范例

1
2
3
4
5
6
7
default_random_engine gen(time(NULL));
uniform_int_distribution<> d1(-233,123456789);
cout<<d1(gen)<<endl;
//output in [-233,123456789]
uniform_int_distribution<long long> d2(numeric_limits<long long>::min(),numeric_limits<long long>::max());
cout<<d2(gen)<<endl;
//output any number in long long

参考文献

  1. http://en.cppreference.com/w/cpp/numeric/random
  2. https://msdn.microsoft.com/en-us/library/windows/desktop/ms644904(v=vs.85).aspx;https://msdn.microsoft.com/en-us/library/windows/desktop/ms644905(v=vs.85).aspx
  3. https://msdn.microsoft.com/en-us/library/windows/desktop/ms724408(v=vs.85).aspx