c++ - 如何在 C++ 中生成没有重复的正态分布？

Question

我试图找到一种快速的方法来生成介于正态分布之间的随机浮点数0，但是从我所看到的所有关于随机数的实现中，这意味着可能存在重复值。1

我的限制是我想产生数百万个数字，比如说 8M 或 16M 等，并避免重复数字。

C++std::normal_distribution也是一个随机生成器。

是否有我寻求的任何实现，或者我是否必须每次检查产生的价值是否已经存在（当我们谈论数百万个数字时，这会真正减慢整个程序的速度）。

我知道正态分布意味着重复，这就是我提出这个问题的原因。

Answer 1

我会使用 astd::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);

---

*）如果您为正态分布选择高标准偏差，则速度很慢。不过，对于小偏差来说，它的速度相当快，因为​​正态分布选择的数字更有可能已经在该范围内。

Answer 2

我的数学有点生疏，所以我希望我没有犯任何可怕的错误。

-1我采用的方法是在和之间增加一个变量+1。然后我计算每个值的正态分布曲线，将其与 [0,1] 之间的随机数进行比较，以决定是否将其包含在输出中。因此，我们越接近平均值，就应该包含更多的值——没有重复。

生成数字并将它们存储在 a 中后，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';
}

Answer 3

下面的机械答案（不是质疑“正常 - 没有重复”）：

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

Answer 4

正态分布意味着您可能在数学期望值附近有许多重复项。当您处理均匀分布时，您的约束是有意义的。