Ошибка в классе «Random» .Net? ⇐ C#

[Anonymous]

Я рассматривал вопрос, в котором говорилось о плохой реализации алгоритма перетасовки Фишера-Йейтса, и был озадачен тем, что при неправильной реализации возникает смещение.
Это два алгоритма:

Код: Выделить всё

private Random _random = new Random();

public int[] FisherYates(int[] source)
{
int[] output = source.ToArray();
for (var i = 0; i < output.Length; i++)
{
var j = _random.Next(i, output.Length);
(output[i], output[j]) = (output[j], output[i]);
}
return output;
}

public int[] FisherYatesBad(int[] source)
{
int[] output = source.ToArray();
for (var i = 0; i < output.Length; i++)
{
var j = _random.Next(0, output.Length);
(output[i], output[j]) = (output[j], output[i]);
}
return output;
}

Очень незначительное отличие, но достаточное, чтобы вызвать массовую предвзятость.
Хорошая реализация:


Плохая реализация:


Чтобы внести ясность в эти графики, я начинаю с чисел от 0 до 99, создаю 10_000_000 тасовок, используя любой алгоритм, а затем усредняю значения в каждой тасовке, чтобы получить единый набор цифр. Если перемешивание действительно случайное, то все 100 цифр будут принадлежать к одному и тому же нормальному распределению.
Все в порядке, но я решил проверить, дают ли эти методы действительные результаты:

Код: Выделить всё

public int[] OrderByRandomNext(int[] source) => source.OrderBy(x => _random.Next()).ToArray();

public int[] OrderByRandomNextDouble(int[] source) => source.OrderBy(x => _random.NextDouble()).ToArray();

Оба хороши и аккуратны, но правильно ли они перемешиваются?

Код: Выделить всё

OrderByRandomNext

:

Код: Выделить всё

OrderByRandomNextDouble

:


Обратили внимание, что цифры 1 и 100 значительно ниже?
Ну, я подумал, что это может быть артефактом того, как OrderBy работает. Поэтому я протестировал его с помощью другого генератора случайных чисел, который нам предоставил Эрик Липперт в его улучшающей серии Random.

Код: Выделить всё

public int[] OrderByBetterRandomNextDouble(int[] source) => source.OrderBy(x => BetterRandom.NextDouble()).ToArray();

public static class BetterRandom
{
private static readonly ThreadLocal crng =
new ThreadLocal(RandomNumberGenerator.Create);

private static readonly ThreadLocal bytes =
new ThreadLocal(() => new byte[sizeof(int)]);

public static int NextInt()
{
crng.Value.GetBytes(bytes.Value);
return BitConverter.ToInt32(bytes.Value, 0) & int.MaxValue;
}

public static double NextDouble()
{
while (true)
{
long x = NextInt() & 0x001FFFFF;
x  algorithm(numbers))
.Aggregate(0.0, (a, v) => a + (double)v[x] / s))
.ToArray())
.Select(x => new
{
averages = x,
distribution = Accord.Statistics.Distributions.Univariate.NormalDistribution.Estimate(x.Skip(1).SkipLast(1).ToArray()),
first = x.First(),
last = x.Last(),
})
.Select(x => new
{
x.averages,
x.distribution,
x.first,
x.last,
first_prob =x.distribution.DistributionFunction(x.first),
last_prob = x.distribution.DistributionFunction(x.last),
})
.ToArray();

var d =

averages.Dump();
}

private Random _random = new Random();

public int[] FisherYates(int[] source)
{
int[] output = source.ToArray();
for (var i = 0; i < output.Length; i++)
{
var j = _random.Next(i, output.Length);
(output[i], output[j]) = (output[j], output[i]);
}
return output;
}

public int[] OrderByRandomNext(int[] source) => source.OrderBy(x => _random.Next()).ToArray();

public int[] OrderByRandomNextDouble(int[] source) => source.OrderBy(x => _random.NextDouble()).ToArray();

public int[] OrderByBetterRandomNextDouble(int[] source) => source.OrderBy(x => BetterRandom.NextDouble()).ToArray();

public static class BetterRandom
{
private static readonly ThreadLocal crng =
new ThreadLocal(RandomNumberGenerator.Create);

private static readonly ThreadLocal bytes =
new ThreadLocal(() => new byte[sizeof(int)]);

public static int NextInt()
{
crng.Value.GetBytes(bytes.Value);
return BitConverter.ToInt32(bytes.Value, 0) & int.MaxValue;
}

public static double NextDouble()
{
while (true)
{
long x = NextInt() & 0x001FFFFF;
x 

Подробнее здесь: [url]https://stackoverflow.com/questions/67888049/bug-in-nets-random-class[/url]