我查看了 std::discrete_distribution 的 gcc libstdc++ 4.7 实现的代码。
权重作为 a 存储vector<double>
在私有成员中。在公共接口中无法访问其 resize 方法。
我将尝试挖掘它的 operator() 的实现(它看起来像在 cpp 中),滚动你自己的应该没有问题。
这是主要动作,我的解释如下:
template<typename _IntType>
void
discrete_distribution<_IntType>::param_type::
_M_initialize()
{
if (_M_prob.size() < 2)
{
_M_prob.clear();
return;
}
const double __sum = std::accumulate(_M_prob.begin(),
_M_prob.end(), 0.0);
// Now normalize the probabilites.
__detail::__transform(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
std::bind2nd(std::divides<double>(), __sum));
// Accumulate partial sums.
_M_cp.reserve(_M_prob.size());
std::partial_sum(_M_prob.begin(), _M_prob.end(),
std::back_inserter(_M_cp));
// Make sure the last cumulative probability is one.
_M_cp[_M_cp.size() - 1] = 1.0;
}
template<typename _IntType>
template<typename _UniformRandomNumberGenerator>
typename discrete_distribution<_IntType>::result_type
discrete_distribution<_IntType>::
operator()(_UniformRandomNumberGenerator& __urng,
const param_type& __param)
{
if (__param._M_cp.empty())
return result_type(0);
__detail::_Adaptor<_UniformRandomNumberGenerator, double>
__aurng(__urng);
const double __p = __aurng();
auto __pos = std::lower_bound(__param._M_cp.begin(),
__param._M_cp.end(), __p);
return __pos - __param._M_cp.begin();
}
所以基本上它在初始化时计算一个辅助向量_M_cp
,它本质上是一个离散的权重累积密度函数。所以产生一个样本仅仅意味着生成一个均匀的随机变量并在累积分布中搜索第一次出现的变量(这是上面的lower_bound调用),返回它的索引。
例如,如果权重向量是:
{ 1, 2, 1, 3 }
那么cp计算如下:
{ 1, 1+2, 1+2+1, 1+2+1+3 }
=
{ 1, 3, 4, 7 }
所以我统一从0..6中选择得到4,所以我选择了第三个。