浅谈随机数生成

· · 算法·理论

扯谈一会

最近在写二叉搜索树，我懂得不多，就再写FHQ\ treap树。写完后，我做测试时发现树形态变化不大，效果不理想。就想着研究随机树生产器。上网查了一下，东西还是蛮多的，就在此整理一下。

优质的随机数生成器：random

其实c++11已经提供了很好的随机数生成器，包含在random头文件，同时需要引用std命名空间。随机数生成器一般会用到一下几种：

mt19937 Rand(seed);

使用梅森旋转算法，效率极高，需要一个种子，生成伪随机数。

mt19937_64 Rand(seed);

同上，只是返回long\ long

random_device Rand;

读取系统熵值或特殊文件，是真随机数，但有局限性，在移植时可能有Bug，有的电脑上多次打开程序会生成一样的数，所以后文不再提到

uniform_int_distribution<T> Rand(L,R);
uniform_real_distribution<T> Rand(L,R);

分别返回L~R的T类型的随机数，原理未知，区别为分别返回整数和浮点数，不推荐使用

高速的随机种子：chrono

根据上文内容，我们基本可以确定我们将用mt19937作为随机数生成器，因为它虽然生成的是伪随机数，但却有极高的随机性，只需要一个高速变化的种子，这样问题就变成了如何获得随机种子。我们当然可以仍用time(0)获得种子，但这样不满足高速变化,就会导致短时间内多次打开程序生成的随机数相同。我们也可以用random\_device生成种子，但前面说了，它某些方面有问题，这里也不用它。那怎么办呢？c++11还包含了一个新库：chrono，包含在chrono头文件，用于获取高精度时间实测可以获取到1/1000000000秒左右，精度已经很高了。

chrono库为我们提供了三种时钟类型：system_clock、steady_clock、high_resolution_clock。这三个时间类都提供了rep（周期）、period（单位比率）、duration（成员类型）。这三个时钟类都提供了一个静态成员函数 now() 用于获取当前时间，该函数的返回值是一个 time_point 类型。

三个时钟的区别：

1.system_clock：类似Windows系统右下角那个时钟，是系统时间。明显这个时钟是可以自己设置的。system_clock除了now()函数外，还提供了to_time_t()静态成员函数。用于将系统时间转换成熟悉的std::time_t类型，得到了std::time_t类型的值，就可以很方便地打印当前时间了。

2.steady_clock：是单调的时钟，相当于教练手中的秒表。只会增长，适合用于记录程序耗时，他表示时钟是不能设置的。

3.high_resolution_clock：是当前系统能够提供的最高精度的时钟。它也是不可以修改的。相当于 steady_clock 的高精度版本。

为了获得更高精度的时间，我会一直使用high_resolution_clock类来获取时间。

现在有了获取时间的工具，但是距离做随机种子还差一步。现在std::chrono::high\_resolution\_clock::now()获取的时间是time_point类型，而且time_point无法直接转成long\ long，也就无法作为随机种子，但它可以用(time\_point对象).time\_since\_epoch().count()将其转为unsigned\ long\ long，就可以作为种子了，获取时间的函数如下：

long long get_high_time(){
    return (std::chrono::high_resolution_clock::now()).time_since_epoch().count();
}

封装成果

至此，理论已经讲完了，完整类代码如下：

#ifndef MYRANDOMS
#define MYRANDOMS
#include<bits/stdc++.h>
#include<chrono>
#include<random>
namespace MTL{
    using namespace std;
    class random{
        public:
        int rand_int(int left,int right){
            static mt19937 engine(get_rand_seed());
            int a=right-left+1,sum;
            sum=engine()%a+left;
            return sum;
        }
        long long operator()(long long left,long long right){
            static mt19937_64 engine(get_rand_seed());
            long long a=right-left+1,sum;
            sum=engine()%a+left;
            return sum;
        }
        long long get_high_time(){
            return (std::chrono::high_resolution_clock::now()).time_since_epoch().count();
        }   
        long long get_rand_seed(){
            mt19937_64 Rand(get_high_time());
            return Rand();
        } 
        random(){

        }
        string rand_string(int len,string char_set){
            int k=char_set.size()-1;
            string re;
            for(int i=0;i<len;i++){
                re+=(char_set[rand_int(0,k)]);
            }
            return re;
        }
    };
}
#endif

代码不长，相信大家看的懂。

(完结)