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))]);
    }
}

09-10 05:25
查看更多