最近准备刷题,打算简单封装下随机数生成器,方便产生测试数据。C++11的STL提供了很多分布类型,比较常用的是均匀分布,均匀分布的值有两种类型,一类是整数,另一类是浮点数,STL根据值的类型定义了两个函数 std::uniform_int_distribution
和 std::uniform_real_distribution
。为了方便使用,我期望在使用的时候通过函数模板的实参推导出要生成的数值类型,而不是显式指定要生成的数值类型。
判断模板实参类型
上面这个需求很简单,最开始想到的方式是对模板实参推断的类型进行判断,根据判断结果做不同的处理。
#include <random>
#include <type_traits>
#include <functional>
#include <limits>
std::default_random_engine e;
template<typename T_>
void Randoms(size_t counts, T_ min, T_ max) {
std::function<T_()> distribute_;
if (std::is_integral<T_>::value) {
// lambda
distribute_ = [=]() {
// 类模板特化 默认result_type int;
std::uniform_int_distribution<> u(min, max);
return u(e);
};
} else {
// 类模板特化 默认result_type double;
std::uniform_real_distribution<> u(min, max);
// std::bind
// 成员函数返回值默认类型为double;
using type_ = double (std::uniform_real_distribution<>::*)
(std::default_random_engine &);
distribute_ = std::bind(
static_cast<type_>(&std::uniform_real_distribution<>::operator()),
&u,
e);
}
for (int i = 0; i < counts; ++i) {
std::cout << distribute_() << " ";
}
std::cout << std::endl;
}
int main(int argc, char **argv) {
Randoms(5,
std::numeric_limits<std::size_t>::min(),
std::numeric_limits<std::size_t>::max());
Randoms(5, -0.5, 0.5);
return 0;
}
从这个测试实例的结果来看,产生的数值远远超过了默认的 int 类型所能表示的数值,然后去看了看具体实现。下面代码是MinGW中GCC的实现版本,从实现中可以看出,均匀分布的类模板重载了函数调用运算符,接收两个参数,一个是均匀分布的随机数生成器,第二个是参数类型。首先定义了三个类型别名:
- 生成器的结果类型 _Gresult_type;
- 无符号的结果类型 __utype,由于类模板推断的结果类型是 int,_utype 的实际类型就是 unsigned int;
- 生成器的结果类型和无符号的结果类型的共同类型 __uctype, 该类型只有当 _Gresult_type 和 __utype 可以相互转换才存在,这个过程实际就是类型转换。
随后使用 __uctype类型别名又定义了下面几个关键的变量,简单来看,生成器相关的属性值(如最大、最小值等)与随机数引擎有关,只要随机数引擎不变,生成器的属性值应该就不会变(至于属性值到底变不变以及是否与随机数种子有关等,待以后有时间再看看那部分源码怎么写的,目前就按不变来理解)。
- __urngmin 表示生成器的最小值,不会改变;
- __urngmax 表示生成器的最大值,不会改变;
- __urngrange 表示生成器的数值范围,不会改变;
- __urange 表示参数类型的数值范围,在放大操作时会随着递归进行改变;
- __ret 表示返回结果的一部分,加上参数范围的最小值即为最终的随机数结果。
当生成器的范围超过了参数类型的范围,那么生成器生成的数值则可能超过参数类型的范围,这时候就需要进行缩小操作。缩小操作首先计算出缩小因子,然后根据缩小因子计算出缩小后符合参数类型的生成器的最大值,只要生成器生成的值超过了允许的最大值则继续生成下一个,直至生成符合要求的数值,最后将生成器的数值按比例缩小。
当生成器的范围低于参数类型的范围,那么就无法生成超过生成器范围,低于参数类型范围的数值,这时候就需要进行放大操作。放大操作是一个循环递归,递归终止的条件则是生成器的范围大于等于参数类型的范围,当生成器生成的值超过了参数类型的范围,说明生成的数值不正确,需要继续重新生成。根据随机数计算公式可以看到,high 的区间是 [0,urange / (urngrange + 1)] ,low 的区间是 [0, urngrange],这两个区间左右两侧都是闭区间,那么根据 (urngrange + 1) * high + low 计算的区间则是[0,urange + low],因此生成的数值可能比 urange大,这个可能性被第一个循环条件处理了。从循环的条件看还有一个判断条件,这个条件还没太理解,初步猜测与数值溢出有一定关系。如果 __tmp 已经处于最大值,此时再加上一个非0的随机数,那么则可能超过 __ret 本身所能表示的范围,导致溢出。
template <typename _IntType>
template <typename _UniformRandomNumberGenerator>
typename uniform_int_distribution<_IntType>::result_type
uniform_int_distribution<_IntType>::
operator()(_UniformRandomNumberGenerator &__urng,
const param_type &__param)
{
typedef typename _UniformRandomNumberGenerator::result_type
_Gresult_type;
typedef typename std::make_unsigned<result_type>::type __utype;
typedef typename std::common_type<_Gresult_type, __utype>::type
__uctype;
const __uctype __urngmin = __urng.min();
const __uctype __urngmax = __urng.max();
const __uctype __urngrange = __urngmax - __urngmin;
const __uctype __urange = __uctype(__param.b()) - __uctype(__param.a());
__uctype __ret;
if (__urngrange > __urange)
{
// downscaling
const __uctype __uerange = __urange + 1; // __urange can be zero
const __uctype __scaling = __urngrange / __uerange;
const __uctype __past = __uerange * __scaling;
do
__ret = __uctype(__urng()) - __urngmin;
while (__ret >= __past);
__ret /= __scaling;
}
else if (__urngrange < __urange)
{
// upscaling
/*
Note that every value in [0, urange]
can be written uniquely as
(urngrange + 1) * high + low
where
high in [0, urange / (urngrange + 1)]
and
low in [0, urngrange].
*/
__uctype __tmp; // wraparound control
do
{
const __uctype __uerngrange = __urngrange + 1;
__tmp = (__uerngrange * operator()(
__urng,
param_type(0, __urange / __uerngrange)));
__ret = __tmp + (__uctype(__urng()) - __urngmin);
} while (__ret > __urange || __ret < __tmp);
}
else
__ret = __uctype(__urng()) - __urngmin;
return __ret + __param.a();
}
std::enable_if 模板元方法
std::enable_if 的定义如下:
template< bool B, class T = void >
struct enable_if;
std::enable_if 实现的功能是根据类模板参数 B 来决定是否定义类型 T 。它是一种元函数,利用 SFINAE 根据类型特征有条件地从重载解析中删除函数,并为不同的类型特征提供单独的函数重载和特化 std :: enable_if 可用作附加函数参数(不适用于运算符重载),返回类型(不适用于构造函数和析构函数)或用作类模板或函数模板参数。参考 https://en.cppreference.com/w/cpp/types/enable_if
SFINAE 是 “Substitution Failure Is Not An Error” 的简写,表示替换失败不是错误,这个规则在函数模板的重载解析中经常被使用,当特化发生替换失败时,这个特化会被从函数集中删除掉,而不是导致一个编译错误。
根据这个原则,只要通过返回值进行区分,就能实现这两个函数的封装了,非常简单明了。
#include <random>
#include <type_traits>
#include <functional>
#include <limits>
#include <algorithm>
class Randoms {
public:
template<typename T_>
std::vector<T_> operator()(std::size_t counts, T_ min, T_ max) {
std::vector<T_> vec;
vec.reserve(counts);
for (int i = 0; i < counts; ++i) {
vec.push_back(generate_(min, max));
}
return std::move(vec);
}
private:
std::default_random_engine e;
template<typename T_>
std::enable_if_t<std::is_integral<T_>::value, T_>
generate_(T_ min, T_ max) {
std::uniform_int_distribution<T_> u(min, max);
return u(e);
}
template<typename T_>
std::enable_if_t<std::is_floating_point<T_>::value, T_>
generate_(T_ min, T_ max) {
std::uniform_real_distribution<T_> u_real(min, max);
return u_real(e);
}
};
int main(int argc, char **argv) {
auto int_result = Randoms()(5,
std::numeric_limits<std::size_t>::min(),
std::numeric_limits<std::size_t>::max());
auto real_result = Randoms()(5, -0.5, 0.5);
for (const auto &ci : int_result) {
std::cout << ci << " ";
}
std::cout << std::endl;
std::for_each(real_result.cbegin(),
real_result.cend(),
[](const auto &cr) { std::cout << cr << " "; });
std::cout << std::endl;
return 0;
}
本博文地址