Как я могу получить независимую от реализации версию std ::iform_int_distribution?
std::uniform_int_distribution принимает любой из <random> PRNG, в том числе те, которые согласованы между реализациями и платформами.
Тем не мение, std::uniform_int_distribution само по себе, похоже, не является согласованным между реализациями, и поэтому я не могу полагаться на то, что смогу их реплицировать, даже используя общий PRNG и seed. Это также влияет на зависимую функциональность, например, 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) является «коротким», но для очень больших диапазонов это может быть проблематично.
Удостоверься что 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))]);
}
}
Другие решения
Образец ответа Джонаса был на самом деле очень полезен. Я извиняюсь за резкую критику. В любом случае, очень важно избегать смещения в равномерном распределении. Самый простой способ добиться этого — это «перемотать», когда значение, предоставленное генератором случайных чисел, выходит за пределы наибольшего диапазона, который допускает несмещенное отображение. Это предполагает, что тип результата генератора имеет, по крайней мере, ту же самую длину битов, что и тип результата распределения (в противном случае может потребоваться использовать несколько значений результата генератора одновременно). Другим важным соображением является избегание целочисленного переполнения, когда b - a + 1 будет переполнен result_type, Итак, есть три основных предостережения:
- Осторожно, если
URNG«sresult_typeимеет меньше битов, чем распределение - Остерегайтесь предвзятости
- Остерегайтесь целочисленного переполнения
Учитывая эти проблемы, неудивительно, что реализация Boost имеет более 150 LOC (включая комментарии). Я бы порекомендовал придерживаться одной из доступных реализаций, если это вообще возможно, потому что это так легко облажаться. Проблема с Boost заключается в том, что алгоритм может меняться с уведомлением или без уведомления между версиями. Вы можете решить эту проблему, скопировав код Boost, чтобы вам не пришлось полагаться на данную версию. Это может означать, что ваша программа может иметь кросс-платформенную совместимость «ошибка за ошибку» — если вам не повезло. (Конечно, эта проблема может возникать с любой реализацией, за исключением доказательственно правильных).
Также, конечно, проверьте условия лицензии перед копированием любого кода библиотеки в ваш проект. Например. Я думаю, что если вы копируете реализацию libstdc ++, это может означать, что вы должны распространять свою программу под GPL и copyleft.