System.Random 的快速替代方案

• 下载源码 - 4.06 Kb

引言

在此我介绍一个可以替代 .NET 框架的 System.Random 类的类，它提供了一些优势。

1. 基于以下论文中指定的简单快速的 XOR-shift 伪随机数生成器 (RNG)：Marsaglia, George. (2003). Xorshift RNGs)。XOR-shift 的这种特定实现具有 2^128-1 的周期。请参阅上述论文，了解如何轻松扩展它以获得更长的周期。在撰写本文时，我找不到关于 System.Random 周期进行比较的信息。
2. 比 System.Random 更快。速度高达 8 倍，具体取决于调用的方法和使用的 CLR (请参阅下表)。
3. System.Random 的直接替代品。此类实现了 System.Random 的所有方法，以及一些用于生成随机 uint 和布尔值的附加方法。同名方法在功能上等同于 System.Random 中的方法。
4. 允许使用种子进行快速重新初始化，这与 System.Random 不同，后者仅在构造时接受种子，然后执行相对耗时的初始化例程。如果您需要多次重置伪随机数序列，例如，如果您想多次重新生成相同的序列，这将提供巨大的速度提升。另一种方法可能是将随机数缓存在数组中，但这种方法受内存容量的限制，并且您可能还需要缓存大量不同的序列。每个序列都可以用一个种子值 (int) 来表示。

背景

我创建 FastRandom 的目的是为了在另一个项目 SharpNEAT 的捕食模拟中获得更高的速度。该模拟要求 RNG 每秒重置给定种子 1000 次。因此，在 FastRandom 的 Reinitialise() 方法在这些情况下可以比 System.Random 提供更好的性能。然后我发现，Next*() 方法还可以进行进一步的性能改进。最初发布在 CodeProject 上的 FastRandom 版本使用了 George Marsaglia 设计的乘加进位 (MWC) 算法。论坛发帖者指出，某些种子会生成相同的数字序列，在调查解决方案时，我偶然发现了 Marsaglia 的另一种利用 XOR-shift 技术来生成随机数的算法，该算法比 MWC 更快。因此，当前版本的 FastRandom 实现的是 XOR-shift，并且应该对所有种子值（包括 0）提供良好的随机序列。

数学

使用的随机数生成器 (RNG) 仅使用按位 XOR 以及左移和右移来生成新数字。NextUInt 方法是最简单的示例，因为它返回生成的 32 位数字 (uint)，而无需进一步处理。

public uint NextUInt() 
{
   uint t= (x^(x<<11)); 
   x=y;
   y=z; 
   z=w;
   return (w= (w^(w>>19))^(t^(t>>8)));
}

RNG 的状态由四个 uint 变量 x、y、z 和 w 描述。w 代表最近生成的数字，并且通过包含 x、y 和 z 变量来维护最后四个已生成数字的历史记录。通过对 x（代表四次调用之前生成的数字）应用各种移位和 XOR 操作来生成新数字。以这种方式存储和使用最后四个数字的历史记录可以得到一个周期更长的 RNG，这里的周期是 2^128-1。通过调整存储的历史变量数量，可以缩短或延长周期。有关更多信息，请参阅上述论文。

所有其他 Next*() 方法都是此技术的变体，它们获取生成的 32 位数字并将其处理成 double、int、byte 等。

Reinitialise() 方法

Reinitialise 方法允许调用者使用单个整数种子值重置 FastRandom，从而重新生成相同的随机数集。这有时会很有用，例如在模拟中，您可能希望完全按照之前的情况重现相同的场景。请注意，System.Random 在类实例化后不提供此类方法来重新初始化 (重新播种)；唯一选择是创建一个新实例并将种子传递给构造函数，然后该构造函数会执行代码来构建一个种子数据数组。通过允许重新初始化并避免构建种子数据数组的需要，FastRandom 在需要重播种时提供了显著的性能改进。

其他性能改进 (与 System.Random 相比)

• 尽可能避免使用浮点算术。这适用于 Next() 和 NextBytes(byte[])。
• 在使用浮点算术时，请确保从 int 转换为 double，而不是从 uint 转换为 double。在测试中，从 uint 转换所需的时间是從 **int** 转换的两倍。此加速适用于 NextDouble()、Next(int) 和 Next(int,int)。
• 不要将方法声明为 virtual。即使在实际运行的、已优化过的代码中，虚拟方法表也会产生一些开销，即使方法实际上没有被重写。System.Random 的方法被声明为 virtual，因此会产生此开销。在 .NET 框架中，这可能有一些合理的理由，但如果您今天只是想要一个快速的 RNG，那么我们可以在声明中省略 virtual 关键字。
• 在 NextBytes 方法中，我们一次生成 32 位，并以 4 字节块填充字节数组。

性能比较表

对于本文的早期读者，请注意，这是表格的更新版本，考虑了自文章首次发布以来 FastRandom.cs 的改进，以及 .NET 运行时引擎在 .NET 1.1 和 .NET 2.0 之间的改进。

其他注意事项

• FastRandom 和 System.Random 在 .NET 2.0 CLR 上的运行速度都比在 .NET 1.1 上快。然而，System.Random 的受益更大，因此在 .NET 2.0 中，两类之间的性能差距会更小。
• 上述观点的一个例外是 Next(int,int)，当两个整数参数之间的范围很长时，在 .Net 1.1 CLR 上 FastRandom 的版本实际上运行得更慢，但在 .NET 2.0 上，正如下面的表格所示，这个结果现在反转了。

以下性能数据是在 Intel Core 2 Duo E660（超频至 3.11Ghz）上运行的已发布、已优化代码获得的。这是一个双核芯片，但这些性能数据仅针对单核。

	System.Random (百万次调用/秒)	FastRandom (百万次调用/秒)	速度提升
Next()	103.252	220.750	2.14x
Next(int)	51.826	142.247	2.14x
Next(int,int)	34.506	87.680	2.54x
Next(int,int) <long 范围>**\***	16.182	30.261	1.87x
NextDouble()	87.680	185.528	2.12x
NextBytes() 测试中为 1024 字节数组	0.105	0.927	8.83x
NextUInt()	不适用	261.437	不适用
NextInt()	不适用	256.081	不适用
NextBool()	不适用	312.500	不适用

**\*** - 当下限和上限之间的范围无法容纳到 int 时，会发生另一种执行路径。这会导致不同的性能数据。

请注意最后三个方法，它们是 System.Random 中不存在的附加方法。NextUint() 提供是因为 uint 是 FastRandom 的底层数据类型，因此生成速度非常快。NextInt() 返回一个 int (Int32<?CODE>)，但与 Next() 不同，其范围在 0 和 int.MaxValue 之间，而不是在 0 和 int.MaxValue-1 之间。这个微妙的区别允许进行优化（消除了一个 'if' 语句）。NextBool() 的实现方式是生成 32 位 (uint) 并将其缓冲起来以供将来调用，因此速度非常快。

结论

System.Random 实际上非常快，其速度主要来自于仅使用简单快速的算术运算，如移位和加法。然而，整个类都围绕着一个返回 0.0 到 1.0 之间 double 的中央 Sample() 方法，因此在生成整数值时会使用一些不必要的浮点算术。FastRandom 使用一种完全不同的随机数生成算法，该算法本身就略快一些，并且在 FastRandom 中，我们通过尽可能避免浮点算术并实现一些进一步的优化来提供额外的提升。最后，FastRandom 还允许快速重新播种，从而可以非常快速地重新生成重复的随机数序列。