Ошибка в классе .Net `Random`?
Я рассматривал вопрос, в котором говорилось о плохой реализации алгоритма перетасовки Фишера-Йейтса, и был озадачен тем, что при неправильной реализации имел место смещение.
Вот два алгоритма:
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;
}
Действительно тонкое различие, но достаточное, чтобы вызвать серьезную предвзятость.
Хорошая реализация:
Плохая реализация:
Теперь все в порядке, но я подумал, что проверю, дают ли эти методы достоверные результаты:
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работает. Поэтому я протестировал его с другим генератором случайных чисел, который был использован Эриком Липпертом в его улучшающей серии случайных чисел.
public int[] OrderByBetterRandomNextDouble(int[] source) => source.OrderBy(x => BetterRandom.NextDouble()).ToArray();
public static class BetterRandom
{
private static readonly ThreadLocal<RandomNumberGenerator> crng =
new ThreadLocal<RandomNumberGenerator>(RandomNumberGenerator.Create);
private static readonly ThreadLocal<byte[]> bytes =
new ThreadLocal<byte[]>(() => 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 <<= 31;
x |= (long)NextInt();
double n = x;
const double d = 1L << 52;
double q = n / d;
if (q != 1.0)
return q;
}
}
}
Что ж, вот график:
Нет предвзятости!
Вот мой код для генерации данных (запускается в LINQPad):
void Main()
{
var n = 100;
var s = 1000000;
var numbers = Enumerable.Range(0, n).ToArray();
var algorithms = new Func<int[], int[]>[]
{
FisherYates,
OrderByRandomNext,
OrderByRandomNextDouble,
OrderByBetterRandomNextDouble,
};
var averages =
algorithms
.Select(algorithm =>
Enumerable
.Range(0, numbers.Length)
.Select(x =>
Enumerable
.Range(0, s)
.Select(y => 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<RandomNumberGenerator> crng =
new ThreadLocal<RandomNumberGenerator>(RandomNumberGenerator.Create);
private static readonly ThreadLocal<byte[]> bytes =
new ThreadLocal<byte[]>(() => 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 <<= 31;
x |= (long)NextInt();
double n = x;
const double d = 1L << 52;
double q = n / d;
if (q != 1.0)
return q;
}
}
}
Вот данные, которые я сгенерировал:
распространение | первый | последний | first_prob | last_prob -------------------------------------------------- ------ | ------------------ | ------------------ | ---------------------- | --------------------- N (x; μ = 49,50267467345823, σ² = 0,0008896228453062147) | 49.505465999987585 | 49.49833699998965 | 0.5372807100387846 | 0,44218570467529394 N (x; μ = 49,50503062243786, σ² = 0,0009954477334487531) | 49.36330799998817 | 49.37124399998651 | 3.529550818615057E-06 | 1,115772521409486E-05 N (x; μ = 49,505720877539765, σ² = 0,0008257970106087029) | 49.37231699998847 | 49.386660999990106 | 1.7228855271333998E-06 | 1,712972513601141E-05 N (x; μ = 49,49994663264188, σ² = 0,0007518765247716318) | 49.50191999998847 | 49.474235999989205 | 0.5286859991636343 | 0,17421285127499514
Вот мой вопрос. Что случилось с
System.Random и предвзятость, которую это вносит?
1 ответ
ГСЧ по умолчанию в .NET до (включительно) .NET 5 имеет известные проблемы смещения и производительности, наиболее документированные здесь https://github.com/dotnet/runtime/issues/23198:
- Опечатка в реализации генератора вычитающих случайных чисел Дональда Кнута с неизвестными практическими эффектами.
- Другой модуль (2^32-1 вместо степени двойки) с неизвестными практическими эффектами.
-
Next(0, int.MaxValue)имеет сильную предвзятость. -
NextDouble()производит только 2^31 возможных значений, из которых можно выбрать прибл. 2^62 различных значения.
Вот почему в .NET 6 реализован лучший алгоритм (xoshiro256**). Вы получите этот лучший ГСЧ, когда создадите экземпляр
new Random()экземпляр без семени. Это описано в https://github.com/dotnet/runtime/pull/47085 . К сожалению, при наличии начального числа заменить старый ГСЧ непросто, поскольку люди могут полагаться на поведение текущего смещенного ГСЧ.
Несмотря на то, что xoshiro256** имеет некоторые задокументированные недостатки (и опровержение ), я обнаружил, что он очень хорошо работает для моих целей. Я скопировал на улучшенную реализацию из .NET 6 и использовать.
Примечание: запросы LINQ обрабатываются лениво (так называемое «отложенное выполнение»). Если вы используете ГСЧ в
.OrderByлямбда, вы можете получить запутанные результаты, если будете повторять несколько раз, потому что порядок может меняться каждый раз. Некоторые алгоритмы сортировки полагаются на тот факт, что элементы не будут внезапно менять свой относительный порядок для правильной работы. Возврат несовместимых значений упорядочения нарушит такие алгоритмы сортировки. Конечно сегодня
OrderByреализация в LINQ-to-Objects работает нормально, но нет документальной гарантии, что она должна работать со «случайным» изменяющимися значениями. Разумная альтернатива -
.OrderBy(e => HashCode.Combine(0x1337, e)).