c++ - 如何获得 std::uniform_int_distribution 的实现不可知版本？

Question

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 }

---

我如何才能正确地实现一个统一的分布，它在不同的平台和标准库实现中是一致的？

Answer 1

这是一个真正均匀分布的示例，使用拒绝抽样来克服模数问题。如果范围 (b - a + 1) 很“短”，则拒绝采样不是问题，但对于非常大的范围，它可能会出现问题。确保 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))]);
    }
}