Какой самый быстрый метод отбора случайных значений из гауссовского распределения? - PullRequest
3 голосов
/ 25 августа 2011

Преобразование Бокса-Мюллера - это элегантный и достаточно эффективный метод выборки случайных значений из гауссовского распределения.

Я ищу более быстрый метод, четко написанный и написанный на C #.

Для справки приведем реализацию реализации Бокса-Мюллера, которая служит базой для сравнений производительности ...

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

Ответы [ 4 ]

6 голосов
/ 12 сентября 2011

Для записи вот четко написанная реализация с юнит-тестами:

ZigguratGaussianDistribution.cs

На моем процессоре Intel Core i7 6700T @ 2,8 ГГц (Skylake) я получаю следующие результаты производительности на одноядерном тесте (с использованием BenchmarkDotNet):

  • Box-Muller: 54,5M выборок / сек
  • Ziggurat: 79,5M образцов / сек

Таким образом, Ziggurat на 45% быстрее в этих тестах.

Оба класса используют Xoshiro256StarStarRandom класс из библиотеки Redzen в качестве источника псевдослучайности.

1 голос
/ 11 февраля 2015

Использование метода для формул очень быстро.У меня нет реализации C #, но я использовал ее в Excel VBA, и она была в 3 раза быстрее по сравнению с подходом Бокса-Мюллера: 70 с на 10 миллионов образцов с использованием Бокса-Мюллера по сравнению с 20 с для 10 миллионов образцов с использованием отношенияединый метод.

enter image description here

удачи.

1 голос
/ 27 августа 2011

Реализация Ziggurat в C:

http://www.seehuhn.de/pages/ziggurat

Также источники GSL (в C) содержат несколько реализаций гауссовых генераторов случайных чисел. Включает методы Бокса-Мюллера и коэффициента.

http://gsl.sourcearchive.com/documentation/1.14plus-pdfsg-1/randist_2gauss_8c-source.html

0 голосов
/ 05 августа 2015

Сэмплирование Ziggurat очень быстро и эффективно использует память.Для приложения C / C ++ вы можете использовать библиотеку GSL

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...