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

Question

我正在尝试找到一种快速的方法来生成 0 和 1 之间的随机 float 数字，这些数字正态分布但来 self 的实现了解所有关于随机数的信息，这意味着可能存在重复值。

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

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

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

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

Answer 1

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

---

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