boost:random 刺骨的言语ヽ痛彻心扉 2023-01-22 03:57 6阅读 0赞 * Boost随机数库(简称Boost.Random)提供了多种[随机数发生器][Link 1] 和[随机数分布器][Link 2], 以产生具有有用属性(例如均匀分布)的(伪)随机数。 #include <boost/random.hpp> using namespace boost; ## 随机数发生器 ## * random库提供了30多个随机数发生器,使用的算法包括线性同余、逆同余、Mersenne Twister、Fibonacci、Ranlunx以及它们的混合。这些随机数发生器的随机数质量、内存需求、产生速度都各不相同,程序员可以仔细评估以选择最适合自己的一个 * 这里推荐三个:rand48、mt19937、lagged\_fibonacci19937,它们产生随机数的速度从高到底,产生的随机数质量和所需内存从低到高 * 虽然这些随机数发生器使用的算法不同,实现也有较大的差异,但是基本接口类似,比如: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70] * 构造函数和成员函数seed()为发生器赋一个种子值 * 静态成员函数min()和max()获取随机数的最大最小值 * operator()产生一个随机数 * generate()填充一个迭代器区间 * 因为随机数序列是固定的,所以也可以使用discard()函数从序列中丢弃一些 #include <iostream> #include <boost/random.hpp> using namespace boost; int main() { boost::mt19937 rng(time(0)); std::cout << mt19937::min() << "<-->" << mt19937 ::max() << "\n"; for(int i = 0; i < 10; i++){ std::cout << rng() << ","; } std::cout << std::endl; // 用随机数填充一个标准容器 rng.discard(5); std::vector<int> vec(10); rng.generate(vec.begin(), vec.end()); for(int i = 0; i < 10; i++){ std::cout << vec[i] << ","; } } 伪随机数发生器在程序中应该尽量少发生构造操作。原因有两个: * 一是伪随机数发生器的构造成本是相当高昂的,越是高质量的伪随机数发生器越需要初始化大量的内部状态,需要大量的时间和空间开销 * 由于构造发生器提供的种子一般是使用系统时间,如果两个发生器构造的时间间隔很短,那么很可能种子值是相同的,从而得到两个行为相同的伪随机数发生器,令随机数失去意义。 随机数发生器允许拷贝、赋值,在某些情况下这种能力是很有用的:拷贝后的副本完全复制了原随机数发生器的状态,可以产生相同的随机数序列,用于再现测试: mt19937 rng(time(0)); std::cout << rng() << std::endl; mt19937 rng2(rng); for (int i = 0;i < 10;++i) { assert(rng() == rng2()); } ## 随机数分布器 ## * 随机数发生器能够产生高质量的随机数,但产生的随机数都是整数类型,均匀分布在整数域。而很多时候我们需要的是某些具有特定要求的随机数,比如在指定区间内的任意整数、\[0,1)区间的实数、整体分布等,前面提到的随机数发生器显然无法满足需求 * 常用的解法是使用模、除以整数最大值等运算处理随机数,使之转变为所要求的数。这种做法虽然可用,但不是最有效的方法。它不具有可复用性,会导致在开发过程中出现大量的重复代码,应该尽量避免 * random库为此提供了[随机数分布器][Link 2]的概念,把随机数发生器产生的整数域随机数映射到另一种分布,提供了代码的复用性 * random库中的很少随机数分布器很多都相当专业,涉及到的数学理论也很深,通常的应用软件开发工作能用的的机会比较少,我们只需要学一些常用的就可以了 * 有了方便设置,有的随机数分布器类内部会定义专门的param\_type类,它相当于一个pair,表示分布使用的参数,通常可以用成员函数a()和b()获得区间的端点 * 随机数分布器同样使用operator()产生随机数,但它需要传入一个随机数发生器作为参数。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1] ### uniform\_smallint ### template<typename IntType = int> class uniform_smallint { public: class param_type { // 内部的param_type 定义 ... }; explicit uniform_smallint(IntType min = 0, IntType max= 9); explicit uniform_smallint(const param_type &); result_type a() const; // 区间左端点 result_type b() const; // 区间右端点 result_type min() const; // 区间左端点 result_type max() const; // 区间右端点 result_type operator()(Engine &) const; result_type operator()(Engine &, const param_type &) const; // 产生随机数 }; uniform\_smallint 实现了在小整数区间的均匀粉笔。它的模板参数是分布的整数类型,默认为int,构造函数指定分布区间的最大最小值。其他接口与伪随机数发生器类似,同样可以用operator(0来获得随机数,同时还提供a()/b()和min()/max()函数返回分布映射的区间范围 ### Uniform\_int\_distribution ### template<typename IntType = int> class Uniform_int_distribution{ public: class param_type { // 内部的param_type 定义 ... }; explicit Uniform_int_distribution(IntType min = 0, IntType max = 9); explicit Uniform_int_distribution(const param_type &); result_type a() const; // 区间左端点 result_type b() const; // 区间右端点 result_type min() const; // 区间左端点 result_type max() const; // 区间右端点 result_type operator()(Engine &) const; result_type operator()(Engine &, const param_type &) const; // 产生随机数 }; * Uniform\_int\_distribution实现了在任意整数区间的均匀分布,它的接口与uniform\_smallint几乎完全相同。两者的区别在于产生随机数分布的质量。uniform\_smallint基于分布区间要远小于随机数源的整数域的假设,不考虑量子化的问题,而Uniform\_int\_distribution则无此限制,分布区间可以是任意大 ### uniform\_01 ### template<typename RealType = double> class uniform_01 { public: result_type min() const; // 区间左端点,总是0 result_type max() const; // 区间右端点,总是1 void reset(); template<typename Engine> result_type operator()(Engine &); //产生随机数 }; uniform\_01 实现了\[0, 1\]区间的小数均匀分布。它的模板参数是产生的浮点数类型,默认是double,其他接口同uniform\_smallint ### uniform\_real\_distribution ### template<typename RealType = double> class uniform_real_distribution { public: class param_type { ... }; explicit uniform_real_distribution(RealType = 0.0, RealType = 1.0); explicit uniform_real_distribution(const param_type &); result_type a() const; // 区间左端点 result_type b() const; // 区间右端点 result_type min() const; // 区间左端点 result_type max() const; // 区间右端点 //产生随机数 template<typename Engine> result_type operator()(Engine &) const; template<typename Engine> result_type operator()(Engine &, const param_type &) const; }; uniform\_real\_distribution 是uniform\_01 在任意实数区间的扩展, 实现了在任意实数区间均匀分布。它的模板参数是产生的浮点数类型,默认是double。构造函数传入实数区间的两个端点,默认位于\[0, 1\], 其他接口同uniform\_smallint ### normal\_distribution ### template<typename RealType = double> class normal_distribution { public: class param_type { ... }; explicit normal_distribution(const RealType & = 0.0, const RealType & = 1.0); explicit normal_distribution(const param_type &); RealType mean() const; //均值 RealType sigma() const; //方差 RealType min() const; RealType max() const; // 产生随机数 template<typename Engine> result_type operator()(Engine &); template<typename URNG> result_type operator()(URNG &, const param_type &); }; normal\_distribution实现了正态分布。它的模板参数是产生的浮点数类型,默认是double。构造函数传入均值和方差(注意它的param\_type表示的不是分布的区间),默认是0和1。成员函数mean()和sigma()分布返回分布的均值和方差 ### 用法 ### 随机数分布器必须搭配随机数发生器才能工作,因此必须先定义一个随机数发生器作为随机数来源,然后再选择一个恰当的模板参数定义一个分布器,把随机数映射到某个区间的分布,最好调用operator()获取所需的随机数 //using namespace boost::random; mt19937 rng(time(0)); random::uniform_int_distribution<> ui(0, 255); for (int i = 0;i < 10;++i) { std::cout << ui(rng) << ","; } assert(ui.a() == 0 && ui.b() == 255); std::cout << std::endl; uniform_01<> u01; for (int i = 0;i < 10;++i) { std::cout << u01(rng) << ","; } std::cout << std::endl; normal_distribution<> nd(1, 2); int count = 0; for (int i = 0;i < 10000;++i) { if (abs(nd(rng) - 1) <= 2.0) { ++count; } } std::cout << 1.0 * count / 10000 << std::endl; 每次运行的结果都不一样,下面是结果之一: ![在这里插入图片描述][2021051715303473.png] ## 变量发生器 ## 有了随机数发生器和分布器,已经基本可以仅仅大部分与随机数相关的问题了。但为了更方便使用,random库还提供了一个模板类variate\_generator(变量发生器),组合了随机数发生器和分布器,使产生随机数更加容易便捷 ### 类摘要 ### * variate\_generator的模板参数是随机数发生器Engine和分布器Distribution ,Engine的类型可以是T,T\*,T&,Distribution 则必须是T,不能是指针或引用 * variate\_generator在构造函数中指定随机数发生器或分布器的实例,可以用engine()、distribution()获取随机数发生器和分布器的引用,operator()产生随机数 template<class Engine, class Distribution> class variate_generator { public: variate_generator(Engine e, Distribution d); result_type operator()(); engine_value_type& engine() ; const engine_value_type& engine() const ; distribution_type& distribution(); const distribution_type& distribution() const; result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const ; result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const ; }; * variate\_generator也可以拷贝和复制,这意味着它和伪随机数发生器一样可以保存状态以便后用,但如果模板参数Engine是引用类型则无法拷贝、赋值 ### 使用 ### mt19937 rng(time(0)); uniform_smallint<> us(1, 100); variate_generator<mt19937&, uniform_smallint<>> gen(rng, us); for(int i = 0; i < 10; i++){ std::cout << gen() << " ; "; } 每次运行的结果都不一样,下面是结果之一: ![在这里插入图片描述][20210517153321409.png] ## 产生随机数据块 ## 随机数分布器和变量发生器一次只能产生一个随机数,但在密码学等领域经常需要产生一定长度的随机数据块。随机数发生器提供了成员函数genrate()可以填充区间,但很遗憾分布器和变量发生器没有这个遍历的成员函数。 我们可以实现模板函数rand\_bytes区间如下: template<typename Rng> void rand_bytes(unsigned char *buf, int buf_len){ typedef variate_generator<Rng, uniform_smallint<>> var_gen_t; static var_gen_t gen(Rng((typename Rng::result_type)time(0)), uniform_smallint<>(1, 255)); //随机字节值在1-255之间 generate_n(buf, buf_len, std::ref(gen)); //for (int i = 0; i < buf_len; ++i) //{ buf[i] = gen();} //循环填入随机数 } * rand\_bytes()要求传入一个随机数发生器模板参数,在内部定义了一个静态变量gen,保证随机数发生器在函数调用时仅会初始化一次,避免了多次构造的代价。 unsigned char buf[10]; rand_bytes<mt19937>(buf, 10); for(int i = 0; i < 10; i++) { std::cout << (short)buf[i] << " , "; } std::cout << std::endl; rand_bytes<rand48>(buf, 10); for(int i = 0; i < 10; i++) { std::cout << (short)buf[i] << " , "; } std::cout << std::endl; 每次运行的结果都不一样,下面是结果之一: ![在这里插入图片描述][20210517155326678.png] ## 真随机数发生器 ## * 之前介绍的随机数发生器产生的都是伪随机数,它们并不是真正的随机数,而是一个非常大的循环周期,真随机数无法用纯软件产生 * 真随机数发生器需要操作系统或者硬件特性支持(比如原子衰变,背景噪声等),为了支持真随机数发生器,random库在头文件`<boost/nondet_random.hpp>`声明了一个random\_device类,它使用桥接模式和pimpl惯用法定义了一个随机数模型,用于可以依据操作系统的特性自行实现真随机数发生器 ### 类摘要 ### class random_device : private noncopyable { public: typedef unsigned int result_type; BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); // 最大/最小值 static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () { return 0; } static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () { return ~0u; } BOOST_RANDOM_DECL random_device(); //默认构造函数 BOOST_RANDOM_DECL explicit random_device(const std::string& token); //用一个名字构造 BOOST_RANDOM_DECL ~random_device(); //析构函数 BOOST_RANDOM_DECL double entropy() const; //熵值 BOOST_RANDOM_DECL unsigned int operator()(); //调用操作符,产生随机数 template<class Iter> void generate(Iter begin, Iter end); //用随机数填充一个迭代区间 private: class impl; //桥接模式,用户自定义实现 impl * pimpl; //使用原始指针,必须手动删除 }; random\_device定义了随机数设备所必须的接口,真正的实现应该是内部类random\_device::impl。注意pimpl指针没有使用smart\_ptr,我们必须自己在ram\_device的析构函数中调用delete来删除它 ### 实现 ### #include <boost/nondet_random.hpp> class boost::random_device::impl { private: rand48 rng; public: impl():rng(time(0)) { std::cout << "random_device::impl ctor\n"; } ~impl() { std::cout << "random_device::impl dtor\n"; } unsigned int operator()() { return rng(); } }; boost::random_device::random_device() : pimpl(new impl) { } boost::random_device::~random_device() { delete pimpl;} double boost::random_device::entropy() const { return 10;} unsigned int boost::random_device::operator()() { return (*pimpl)();} void case6() { random_device rng; for (int i = 0 ;i < 10 ; ++i) { std::cout << rng() << ","; } std::cout << std::endl; uniform_real<> ur(1.0, 2.0); for (int i = 0 ;i < 10 ; ++i) { std::cout << ur(rng) << ","; } std::cout << std::endl; variate_generator<random_device&, uniform_smallint<>> gen(rng, uniform_smallint<>(0,255)); for (int i = 0 ;i < 10 ; ++i) { std::cout << gen() << ","; } std::cout << std::endl; } [Link 1]: https://www.boost.org/doc/libs/1_76_0/doc/html/boost_random/reference.html#boost_random.reference.generators [Link 2]: https://www.boost.org/doc/libs/1_76_0/doc/html/boost_random/reference.html#boost_random.reference.distributions [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20221020/5f467942fd294f28b068e9c6c10164af.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20221020/cdfcf074ba614cb4bca43ac862a75e70.png [2021051715303473.png]: /images/20221020/8651ad5937e84affb852c487971d098a.png [20210517153321409.png]: /images/20221020/da06f76266ec4449b3aaca2a3496ea7c.png [20210517155326678.png]: /images/20221020/9311d238d6ed49359c521dc20ac76b65.png
还没有评论,来说两句吧...