.Net 的“随机”class 中存在错误?
Bug in .Net's `Random` class?
我正在看一个关于 Fisher-Yates 改组算法实施不当的问题,我很困惑,因为实施不当会产生偏差。
这两个算法是:
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
工作原理的产物。因此,我用另一个随机数生成器对其进行了测试 - 埃里克·利珀特 (Eric Lippert) 在其改进的随机数列中使用的一个生成器。
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
和它引入的偏差是怎么回事?
直到(包括).NET 5 的 .NET 中的默认 RNG 具有已知的偏差和性能问题,大部分记录在此处 https://github.com/dotnet/runtime/issues/23198:
- 执行 Donald E. Knuth 的减法随机数生成器时出现错字,实际效果未知。
- 实际效果未知的不同模数(2^32-1 而不是 2 的幂)。
Next(0, int.MaxValue)
有严重的偏见。
NextDouble()
只产生 2^31 个可能的值,它可以从大约中选择。 2^62 个不同的值。
这就是 .NET 6 实现更好算法的原因(xoshiro256**). You will get this better RNG when you instantiate a new Random()
instance without a seed. This is described in https://github.com/dotnet/runtime/pull/47085。不幸的是,在提供种子时替换旧的 RNG 并不容易,因为人们可能依赖于当前有偏见的 RNG 的行为.
即使 xoshiro256** 有一些 documented flaws (and a rebuttal) as well, I found it to work pretty well for my purposes. I have copied the improved implementation from .NET 6 并使用它。
旁注:LINQ 查询是延迟计算的(a.k.a。“延迟执行”)。如果您在 .OrderBy
lambda 中使用 RNG,那么如果您多次迭代,您可能会得到令人困惑的结果,因为顺序可能每次都不同。一些排序算法依赖于这样一个事实,即元素不会突然改变它们的相对顺序才能正常工作。返回不一致的排序值将破坏此类排序算法。当然,今天 LINQ-to-Objects 中的 OrderBy
实现工作正常,但没有书面保证它必须使用“随机”变化的值。一个合理的选择是 .OrderBy(e => HashCode.Combine(0x1337, e))
.
我正在看一个关于 Fisher-Yates 改组算法实施不当的问题,我很困惑,因为实施不当会产生偏差。
这两个算法是:
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
工作原理的产物。因此,我用另一个随机数生成器对其进行了测试 - 埃里克·利珀特 (Eric Lippert) 在其改进的随机数列中使用的一个生成器。
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
和它引入的偏差是怎么回事?
直到(包括).NET 5 的 .NET 中的默认 RNG 具有已知的偏差和性能问题,大部分记录在此处 https://github.com/dotnet/runtime/issues/23198:
- 执行 Donald E. Knuth 的减法随机数生成器时出现错字,实际效果未知。
- 实际效果未知的不同模数(2^32-1 而不是 2 的幂)。
Next(0, int.MaxValue)
有严重的偏见。NextDouble()
只产生 2^31 个可能的值,它可以从大约中选择。 2^62 个不同的值。
这就是 .NET 6 实现更好算法的原因(xoshiro256**). You will get this better RNG when you instantiate a new Random()
instance without a seed. This is described in https://github.com/dotnet/runtime/pull/47085。不幸的是,在提供种子时替换旧的 RNG 并不容易,因为人们可能依赖于当前有偏见的 RNG 的行为.
即使 xoshiro256** 有一些 documented flaws (and a rebuttal) as well, I found it to work pretty well for my purposes. I have copied the improved implementation from .NET 6 并使用它。
旁注:LINQ 查询是延迟计算的(a.k.a。“延迟执行”)。如果您在 .OrderBy
lambda 中使用 RNG,那么如果您多次迭代,您可能会得到令人困惑的结果,因为顺序可能每次都不同。一些排序算法依赖于这样一个事实,即元素不会突然改变它们的相对顺序才能正常工作。返回不一致的排序值将破坏此类排序算法。当然,今天 LINQ-to-Objects 中的 OrderBy
实现工作正常,但没有书面保证它必须使用“随机”变化的值。一个合理的选择是 .OrderBy(e => HashCode.Combine(0x1337, e))
.