Как произвести нормальное распространение без дубликатов в C ++?
Я пытаюсь найти быстрый способ производить случайные поплавок числа между 0 а также 1 нормально распределенный, но из реализаций, которые я видел, все дело в случайных числах, означающих, что возможны повторяющиеся значения.
Мое ограничение в том, что я хочу производить миллионы чисел, скажем, 8M или 16M и т. д. и избегать повторяющихся номеров.
C ++ std::normal_distribution также является генератором случайных чисел.
Есть ли какая-либо реализация того, что я ищу, или мне нужно каждый раз проверять, существует ли уже произведенная стоимость (что действительно замедлит всю программу, когда мы говорим о миллионах чисел).
Я знаю, что нормальное распределение подразумевает дубликаты, поэтому я открыл этот вопрос.
Решение
Я бы решил эту проблему, используя std::unordered_set проверить уже сгенерированные номера. Это ожидало постоянного времени для проверки и вставки, поскольку оно основано на хэш-таблице; суммирование до линейной сложности времени в количестве генерируемых чисел N,
Универсальное решение, которое работает с любым дистрибутивом:
template <typename T, typename Dist, typename Gen>
std::unordered_set<T> unique_generate(Dist &&dist, Gen &&generator, size_t N)
{
std::unordered_set<T> generated;
while (generated.size() < N)
generated.insert(dist(generator));
return generated;
}
Использование с normal_distribution:
std::random_device rd;
std::mt19937 gen(rd());
std::normal_distribution<double> d(meanValue, stdDevValue);
int N = 1000000;
auto myNumbers = unique_generate<double>(d, gen, N);
Чтобы также обеспечить выполнение чисел в интервале [0, 1]Вы можете обернуть объект распределения, используя универсальный класс-оболочку («разделение задач»: не смешивайте уникальную генерацию с ограничением распределения).
Возможная (возможно, медленная *) реализация отбрасывает сгенерированные числа, которые выходят за пределы:
template<typename Dist, typename T>
class ClampedDistribution {
Dist dist;
T min, max;
public:
ClampedDistribution(Dist dist, T min, T max) :
dist(dist), min(min), max(max)
{}
template <typename Gen>
auto operator()(const Gen & generator) -> decltype(dist(generator)) {
auto value = dist(generator);
while (value > max || value < min)
value = dist(generator);
return value;
}
};
// type-deducing function:
template<typename Dist, typename T>
ClampedDistribution<Dist,T> clamped(Dist dist, T min, T max) {
return ClampedDistribution<Dist,T>(dist, min, max);
}
Использование:
// (from above)
std::normal_distribution<double> d(meanValue, stdDevValue);
// clamp it:
auto clamped_dist = clamped(d, 0.0, 1.0);
// and pass this to unique_generate:
auto myNumbers = unique_generate(clamped_dist, gen, N);
*) Это медленно, если вы выбираете высокое стандартное отклонение для вашего нормального распределения. Это достаточно быстро для небольших отклонений, так как числа, выбранные нормальным распределением, с большей вероятностью уже находятся в диапазоне.
Другие решения
Моя математика немного ржавая, поэтому я надеюсь, что не допустил никаких ужасных ошибок.
Подход, который я выбрал, заключался в увеличении переменной между -1 а также +1, Затем я вычисляю кривую нормального распределения для каждого значения, сравнивая ее со случайным числом в диапазоне [0,1], чтобы решить, включать его или нет в выходные данные. Таким образом, чем ближе мы к среднему значению, тем больше значений должно быть включено — без дубликатов.
После генерации чисел и сохранения их в std::vector Я выполняю случайное перемешивание:
#include <cmath>
#include <random>
#include <iostream>
#include <algorithm>
double normal(double x, const double mu, const double sigma)
{
double fac = 1 / (sigma * sqrt(2 * M_PI));
double exp = pow(x - mu, 2) / (2 * sigma * sigma);
return fac * pow(M_E, -exp);
}
// res = resolution (distance between samples) [res < 1]
std::vector<double> generate(double res, const double mu, const double sigma)
{
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> dis(0, 1);
std::vector<double> values;
for(double x = -1; x < 1; x += res)
if(dis(gen) < normal(x, mu, sigma))
values.push_back(x);
std::shuffle(values.begin(), values.end(), gen);
return values;
}
int main()
{
std::vector<double> values = generate(0.000001, 0, 1);
std::cout << values.size() << '\n';
for(auto v: values)
std::cout << v << '\n';
}
РЕДАКТИРОВАТЬ: Улучшенная версия:
Добавлена параметризация ассортимента.
Улучшена доходность.
// normal probability density function
double normal_pdf(const double x, const double mu, const double sigma)
{
double fac = 1 / (sigma * sqrt(2 * M_PI));
double exp = pow(x - mu, 2) / (2 * sigma * sigma);
return fac * pow(M_E, -exp);
}
/**
* Randomly generate unique values between [i0, i1)
* with a normal distribution.
*
* @param i0 The lower, inclusive bound of the range
* of the generated values.
*
* @param i1 The upper, exclusive bound of the range
* of the generated values.
*
* @param res The resolution. The size between samples when
* calculating the values (< 0).
*
* @param mu The mean value of the distribution PDF
*
* @param sigma The Standard Deviation of the PDF.
*
* @return A std::vector<double> containing thegenerated
* values.
*/
std::vector<double> generate(const double i0, const double i1
, const double res, const double mu, const double sigma)
{
std::random_device rd;
std::mt19937 gen(rd());
std::vector<double> values;
double maximum = normal_pdf(mu, mu, sigma);
std::uniform_real_distribution<> dis(0, maximum);
for(double x = i0; x < i1; x += res)
if(dis(gen) < normal_pdf(x, mu, sigma))
values.push_back(x);
std::shuffle(values.begin(), values.end(), gen);
return values;
}
int main()
{
std::vector<double> values = generate(0, 1, 0.01, 0.5, 1);
std::cout << values.size() << '\n';
for(auto v : values)
std::cout << v << '\n';
}
Механический ответ (без вопросов «нормально — без дубликатов») ниже:
using gen = std::normal_distribution<long>(_1, _2);
std::set<long> data; // if you want to use double you'll need to customize the comparator
std::generate(std::inserter(data, data.end()), _3, gen);
Нормальное распределение означает, что у вас может быть много дубликатов около математического ожидаемого значения. Ваше ограничение имеет смысл, когда вы имеете дело с равномерным распределением.