std::uniform_int_distribution
接受<random
>的任何PRNG,包括在实现和平台之间一致的PRNG。
但是,std::uniform_int_distribution
本身在实现之间似乎并不一致,因此即使使用通用的PRNG和种子,我也不能依靠能够复制它们。这也会影响相关的功能,例如std::shuffle()
。
因此,例如:
#include <random>
#include <iostream>
#include <string>
#include <algorithm>
template<typename T>
void printvector(const std::string& title, const std::vector<T>& v)
{
std::cout << title << ": { ";
for (const auto& val : v) { std::cout<<val<<" "; }
std::cout << "}" << std::endl;
}
int main()
{
const static size_t SEED = 770;
std::minstd_rand r1(SEED), r2(SEED), r3(SEED);
std::vector<int> vPRNG;
for (int i=0; i<10; ++i) { vPRNG.push_back((int)r1()); }
std::vector<size_t> vUniform;
std::uniform_int_distribution<int> D(0,301);
for (int i=0; i<10; ++i) { vUniform.push_back(D(r2)); }
std::vector<size_t> vShuffled {1,2,3,4,5,6,7,8,9,10};
std::shuffle(vShuffled.begin(), vShuffled.end(), r3);
printvector("PRNG", vPRNG);
printvector("UniformDist", vUniform);
printvector("Shuffled", vShuffled);
}
即使PRNG本身生成的数字完全相同,在不同的系统上也会给我不同的结果:
系统1:
PRNG: { 37168670 1020024325 89133659 1161108648 699844555 131263448 1141139758 1001712868 940055376 1083593786 }
UniformDist: { 5 143 12 163 98 18 160 140 132 152 }
Shuffled: { 7 6 5 2 10 3 4 1 8 9 }
系统2:
PRNG: { 37168670 1020024325 89133659 1161108648 699844555 131263448 1141139758 1001712868 940055376 1083593786 }
UniformDist: { 19 298 170 22 53 7 43 67 96 255 }
Shuffled: { 3 7 4 1 5 2 6 9 10 8 }
如何正确实现在不同平台和标准库实现之间一致的统一分发?
最佳答案
这是一个真正均匀分布的示例,使用拒绝采样来克服模数问题。如果范围(b - a + 1
)为“short”,则拒绝采样不是问题,但对于很大的范围,可能会出现问题。
确保b - a + 1
不下溢/溢出。
template <class IntType = int>
struct my_uniform_int_distribution
{
using result_type = IntType;
const result_type A, B;
struct param_type
{
const result_type A, B;
param_type(result_type aa, result_type bb)
: A(aa), B(bb)
{}
};
explicit my_uniform_int_distribution(const result_type a = 0, const result_type b = std::numeric_limits<result_type>::max())
: A(a), B(b)
{}
explicit my_uniform_int_distribution(const param_type& params)
: A(params.A), B(params.B)
{}
template <class Generator>
result_type operator()(Generator& g) const
{
return rnd(g, A, B);
}
template <class Generator>
result_type operator()(Generator& g, const param_type& params) const
{
return rnd(g, params.A, params.B);
}
result_type a() const
{
return A;
}
result_type b() const
{
return B;
}
result_type min() const
{
return A;
}
result_type max() const
{
return B;
}
private:
template <class Generator>
result_type rnd(Generator& g, const result_type a, const result_type b) const
{
static_assert(std::is_convertible<typename Generator::result_type, result_type>::value, "Ups...");
static_assert(Generator::min() == 0, "If non-zero we have handle the offset");
const result_type range = b - a + 1;
assert(Generator::max() >= range); // Just for safety
const result_type reject_lim = g.max() % range;
result_type n;
do
{
n = g();
}
while (n <= reject_lim);
return (n % range) + a;
}
};
template<class RandomIt, class UniformRandomBitGenerator>
void my_shuffle(RandomIt first, RandomIt last, UniformRandomBitGenerator&& g)
{
typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
typedef my_uniform_int_distribution<diff_t> distr_t;
typedef typename distr_t::param_type param_t;
distr_t D;
diff_t n = last - first;
for (diff_t i = n-1; i > 0; --i)
{
std::swap(first[i], first[D(g, param_t(0, i))]);
}
}