C#生成随机整数 - 神秘之谜

Question

我在生成随机整数时发现了一些有趣的事情（至少对我来说），但我无法自己解释，所以我想在这里发布它。

我的需求很简单：我正在生成随机整数（Int32）ID，并且旨在最小化碰撞。生成时间不是问题。

我尝试了以下几种方法来生成随机整数：

1.)

   return rnd.Next();

其中rnd是类型为Random的类字段，其种子来源于方法#3。

2.)

   return rnd.Next(Int32.MinValue, Int32.MaxValue);

在这里，rnd 再次是类型为 Random 的类字段，并且其种子来自第三个方法。

3.)

   var buffer = new byte[sizeof(int)];
   using (var rng = new RNGCryptoServiceProvider())
   {
        rng.GetBytes(buffer);
   }            
   return BitConverter.ToInt32(buffer, 0);

注意：我还尝试将RNGCryptoServiceProvider作为类字段在包含类的初始化时初始化一次，以便减轻GC的工作，但是生成所需时间相同，因此我认为这样会更“随机”。

4.)

   return new Random(Method3()).Next();

5.)

   return new Random(Method3()).Next(Int32.MinValue, Int32.MaxValue);

我知道，每次创建新的Random(int seed)都很耗时间，但是碰撞较少，对吧？

现在是神秘部分。我假设大多数碰撞会有方法#1和#2，其中#1会稍微快一些，更少碰撞，而最少碰撞的方法将是#4和#5，其中#4会稍微快一些，更少碰撞，并且方法#3将是某种妥协。

所以我进行了一个测试来证明我的假设。我使用每种方法生成了10倍（为了平均）100万个随机数，并记录了平均碰撞次数和生成100万个数字所需的平均时间。以下是结果，对我来说有点惊讶。

结果：持续时间以小时：分钟：秒：毫秒的格式呈现。

Method1: AvgCollisions: 235, AvgDuration: 00:00:00.3561967
Method2: AvgCollisions: 116, AvgDuration: 00:00:00.4042033
Method3: AvgCollisions: 115, AvgDuration: 00:00:04.6037259
Method4: AvgCollisions: 234, AvgDuration: 00:00:09.2195856
Method5: AvgCollisions: 233, AvgDuration: 00:00:09.1788223

我再次运行了几次测试，结果基本相同。你也觉得很奇怪吗？虽然这些时间并没有给我带来惊喜，但对我而言，结果意味着Method2是生成随机数最好的方法，因为它是最随机、最快速且可以设置最小和最大生成数字。不知道Method2相对于Method3更可预测多少，因为我不知道该如何测试它。

有人能解释一下我错在哪里或者为什么方法#4和#5没有最小碰撞率，以及为什么碰撞率始终保持一致吗？这不应该是随机的吗？

编辑：这里是我做这个测试所用的Visual Studio 2010解决方案：http://bit.ly/nxLODw

- MSkuta

---

你对第一个结果中看到的碰撞数量确定吗？在这里(和其他无数类似的讨论中——这是编程中五个最常见的误解之一)的启发下，其他一切都是有意义的。你能发表你的测试用例吗？ - Michael Petrotta

你的第四/第五个假设是错误的。你永远不应该为每个需要随机数的地方调用 new Random()。只需执行一次即可。 - Jesse C. Slicer

+1 给 Michael Petrotta。还有无数类似的讨论在这里。 - L.B

给Michael Petrotta：我发布了VS2010解决方案，正在编辑中。我知道Random类默认由系统时钟种子化，这就是为什么我每次都从RNGCryptoServiceProvider中获取新的随机种子，或者它是指在每个Next()调用中使用系统时钟进行计算？ - MSkuta

Answer 1

唯一奇怪的行为出现在方法5中。

在方法1和4中，你生成一个介于0到int.MaxValue范围内的数字。

在方法2、3和5中，你生成一个介于int.MinValue到int.MaxValue范围内的数字。

因此，在方法2和3中，你有一个大约两倍大的范围，并且与方法1和4相比，它们有约一半的碰撞。这对我来说似乎很正常。

那么为什么方法5会产生与方法1和4相同数量的碰撞，即使它生成了更大的范围内的数字呢？嗯，事实证明，System.Random构造函数取种子的绝对值。换句话说，它将随机序列的数量减少了一半。因此，即使你从更大的范围内获得数字，你也是从较少不同的序列中生成它们的。

- Jeffrey Sax

---

你说得对。我不知道怎么会错过那个1和4只生成正数的事实..现在我明白了，谢谢。 - MSkuta

现在出现了一个新问题，为什么所有的方法都有相同数量的碰撞？方法3不应该有最少的碰撞吗？因为它是RNGCrypto... - MSkuta

不完全是这样。即使在“真正”的随机序列中，您仍然会遇到碰撞。由于您只生成了可能数字的约1/2000或1/4000，因此您的密度太低，无论如何都看不到任何差异。 - Jeffrey Sax

关于 System.Random 和 RNGCrypto 的区别：主要的区别在于用途。System.Random 是通用型的随机数生成器，而 RNGCrypto... 则是专门设计用来击败对随机数生成序列重构的攻击。许多其他类型的随机数生成器，你可以从序列中有限数量的值推断出整个序列（因此预测其余部分）。 - Jeffrey Sax

Answer 2

当你在那里的时候，你可能想把#3改成：

        var buffer = new byte[sizeof(int)];

        using (var rng = new RNGCryptoServiceProvider())
        {
            rng.GetBytes(buffer);
        }

        return BitConverter.ToInt32(buffer, 0);

这样做可以a）确保您的数组大小为int（而不是神奇数字4），并且b）正确处理RNGCryptoServiceProvider的IDisposable。

- Jesse C. Slicer