如何获得一个与实现无关的std :: uniform_int_distribution版本？

Question

如何获得一个与实现无关的std :: uniform_int_distribution版本？

8

std::uniform_int_distribution可以接受<random>的任何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 }

如何正确实现一个统一分布，以保证在不同平台和标准库实现下的一致性？

- Ziv

6

要么自己构建，要么包含第三方库，例如boost。 - NathanOliver

1

@NathanOliver: 我不知道boost是否比c++11提供更好的保证。我尝试使用Crypto ++ 进行了检查，结果也有所不同。这使我认为，自己实现可能比听起来更复杂... 如果您能指出一个第三方库可以给出保证，或者提供一个（非平台依赖的）自己实现的方向，我将不胜感激。 - Ziv

Boost的分发应该是可移植的，因为它使用相同的实现。标准版本则不是这样，因为即使它们定义了概率，也有多种实现方法可以达到目的，而不同的供应商可能会使用它们。 - NathanOliver

一个简单的方法是选择某个供应商的std::uniform_int_distribution实现，并将其复制到另一个命名空间中（注意适当的许可证）。 - Caleth

1

Boost通常提供较弱的兼容性保证。例如（二进制）Boost.Serialization 1.58.0 可能与1.59.0或跨平台不兼容。 Boost的 uniform_int_distribution 的实现可能不太可能改变，但我仍然不会依靠它。 - Arne Vogel

2个回答

2

来自 Jonas 答案的样板非常有用。对于我之前的苛刻批评，我感到很抱歉。无论如何，在均匀分布中避免偏差非常重要。最简单的方法是在随机生成器提供的值超出允许无偏映射的最大范围时进行“重新投掷”。这假设生成器的结果类型至少具有与分布结果类型相同的位长度（否则可能需要同时使用多个生成器结果值）。另一个重要的考虑因素是在 b - a + 1 溢出 result_type 时避免整数溢出。因此，存在三个主要注意事项：

如果 URNG 的 result_type 比分布的少，则要小心
要注意偏差
要注意整数溢出

鉴于这些挑战，Boost 的实现代码包括注释在内有 150 多行。如果有可能，我建议坚持使用可用的实现，因为这很容易搞砸。 Boost 的问题在于算法可能会在版本之间更改，有或没有通知。您可以通过复制 Boost 代码来解决这个问题，以便不必依赖于特定版本。如果你不幸的话，这可能意味着你的程序可能具有跨平台“bug for bug”的兼容性。（当然，除了可证明正确的实现之外，任何实现都可能出现此问题。）

在将任何库代码复制到您的项目中之前，显然要检查许可条款。例如，我认为如果你复制 libstdc++ 的实现，这可能意味着你必须在 GPL 和 copyleft 下分发你的程序。

- Arne Vogel

1

你提出了一些好观点。在我的新答案中，我没有处理 b - a + 1 的溢出可能性，但其他方面都已经处理好了。 - Jonas

你能详细说明为什么避免偏见非常重要吗？就我个人而言，我从来没有真正需要完美的均匀分布。 - Jonas

1

@Jonas：对于任何特定的使用，这可能不是一个问题！但作为其他代码视为理所当然的基础实用程序，非均匀性可能是一个非常难以察觉且具有严重后果的错误。最好一次性完美解决，而不是每次都需要检查“好的，这次是否足够公正？” - Ziv

@Ziv 这是一个公正的观点。但是，考虑到建议的实现方式，它也引发了一个新问题：“好的，这个‘重新投掷’技术这次我能容忍吗？” - Jonas

1

@Jonas 可能是我的个人偏见，认为库代码应该做它承诺的事情，正如Ziv所提到的。获取更多的输入值具有无限最坏情况性能的明显劣势，在实时（特别是关键任务）系统中可能是不可接受的，但是再次，OP要求的是统一性而不是速度。 - Arne Vogel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonas · Accepted Answer

这是一个使用拒绝采样方法来克服模数问题的均匀分布示例。如果范围（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))]);
    }
}