logo标签列表

从高斯分布中抽样的最快方法是什么？

c#performancemathgaussiansampling
4

Box-Muller变换是从高斯分布中抽样随机值的一种优雅且性能良好的方法。

我正在寻找一个更快、清晰且使用C#编写的方法。

以下是一个实现Box-Muller算法用于性能比较的基准代码……

public class GaussianGenerator
{
    FastRandom _rng = new FastRandom();
    double? _spareValue = null;

    /// <summary>
    /// Get the next sample point from the gaussian distribution.
    /// </summary>
    public double NextDouble()
    {
        if(null != _spareValue)
        {
            double tmp = _spareValue.Value;
            _spareValue = null;
            return tmp;
        }

        // Generate two new gaussian values.
        double x, y, sqr;

        // We need a non-zero random point inside the unit circle.
        do
        {
            x = 2.0 * _rng.NextDouble() - 1.0;
            y = 2.0 * _rng.NextDouble() - 1.0;
            sqr = x * x + y * y;
        }
        while(sqr > 1.0 || sqr == 0);

        // Make the Box-Muller transformation.
        double fac = Math.Sqrt(-2.0 * Math.Log(sqr) / sqr);

        _spareValue = x * fac;
        return y * fac;
    }

    /// <summary>
    /// Get the next sample point from the gaussian distribution.
    /// </summary>
    public double NextDouble(double mu, double sigma)
    {
        return mu + (NextDouble() * sigma);
    }
}
你是否有一个优雅的C#实现Ziggurat算法的代码？ - redcalx
1
你想要速度和优雅吗？实现比例-均匀算法！在我看来，Ziggurat 算法很丑陋，而且调整起来非常困难。 - Alexandre C.
@Alexadre。到目前为止，我已经花了几天时间编写一个尽可能优雅的版本，但是它比例如Box-Muller要复杂得多，特别是在优化之后！我没有听说过比值法则，我会研究一下的，感谢你的指引。 - redcalx
不确定为什么这个问题被关闭了，对我来说它看起来是一个完全有效的与编程有关的问题，即产生高斯噪声是一个非常常见的需求，同样需要高效快速地实现。 - redcalx
4个回答
6
以下是一份清晰的实现，附带单元测试：ZigguratGaussianDistribution.cs。在我的Intel Core i7 6700T @ 2.8Ghz (Skylake)上进行单核测试（使用BenchmarkDotNet），性能结果如下：
  • Box-Muller：每秒54.5M个样本
  • Ziggurat：每秒79.5M个样本
因此，在这些测试中，Ziggurat快了约45%。 这两个类都使用Redzen库中的Xoshiro256StarStarRandom类作为伪随机源。
1
我已经纠正了所有的链接。编辑在审核队列中。 - Xharlie
1
@Xharlie，我已经编辑了你的修改。那些sourceforge链接是软件的旧版本，我应该删除它们。现在所有内容都在https://github.com/colgreen/Redzen/tree/master/Redzen/Numerics。 - redcalx
@Xharlie 实际上，那个sourceforge版本中存在一个错误，使得连续的高斯值相关联，如果在（x，y）笛卡尔图上绘制两个连续的值，这一点就会变得明显。 - redcalx
@redcalx 太棒了。现在我知道哪个是最好的版本了。顺便说一下 - Redzen 版本包含一条注释，说明 RNG 在 Math.NET 中被分叉，但我检查了 Math.NET 代码库，其中的 XorShift RNG 完全不同于 Redzen 的。我想 Redzen 的可能是更好的选择。 - Xharlie
@Xharlie，它被分叉了，然后有人用一个乘法和移位的随机数生成器替换了整个文件的内容，但没有改变类名！ - redcalx
ZigguratGaussianDistribution.cs 的链接无法使用。 - Kresimir
2
使用比例-均匀分布方法非常快速。虽然我没有C#实现，但我在Excel VBA中使用它时，与Box-Muller方法相比，速度快了3倍：使用Box-Muller进行1000万个样本需要70秒，而使用比例-均匀分布方法只需要20秒。

enter image description here

祝你好运。
1
0

Ziggurat抽样非常快速和内存高效。对于C/C++应用程序，您可以使用GSL库。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接