随机并行生成数字 1 的次数超过 90%

本文关键字：并行 数字 随机 | 更新日期: 2023-09-27 18:36:47

请考虑以下程序：

public class Program
{
     private static Random _rnd = new Random();
     private static readonly int ITERATIONS = 5000000;
     private static readonly int RANDOM_MAX = 101;
     public static void Main(string[] args)
     {
          ConcurrentDictionary<int,int> dic = new ConcurrentDictionary<int,int>();
          Parallel.For(0, ITERATIONS, _ => dic.AddOrUpdate(_rnd.Next(1, RANDOM_MAX), 1, (k, v) => v + 1));
          foreach(var kv in dic)
             Console.WriteLine("{0} -> {1:0.00}%", kv.Key, ((double)kv.Value / ITERATIONS) * 100);
     }
}

这将打印以下输出：

（请注意，每次执行时输出都会有所不同）

> 1 -> 97,38%
> 2 -> 0,03%
> 3 -> 0,03%
> 4 -> 0,03%
...
> 99 -> 0,03%
> 100 -> 0,03%

为什么数字 1 以这样的频率生成？

随机并行生成数字 1 的次数超过 90%

Random不是线程安全的。

Next 在确保线程安全方面没有任何特殊作用。

不要像这样使用Random。并且也不考虑使用线程本地存储持续时间，否则会弄乱生成器的统计属性：您只能使用一个Random实例。一种方法是使用lock(_global)并在该锁定区域中绘制一个数字。

我认为这里发生的事情是，到达生成器的第一个线程正确生成其随机数，并且所有后续线程为每个绘图接收 0。使用 32 个线程的"并行化"线程池，您上面引用的比率大致达到;假设 31 个线程的结果放置在第一个存储桶中。

从线程本地存储解决方案更进一步，并试图避免统计问题，我建议使用从RNGCryptoServiceProvider生成的随机种子：

using System;
using System.Collections.Concurrent;
using System.Threading;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
    class Program
    {
        private static readonly int ITERATIONS = 5000000;
        private static readonly int RANDOM_MAX = 101;
        private static int GetCriptoRandom()
        {
            using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
            {
                byte[] bytes = new byte[4];
                rng.GetBytes(bytes);
                return BitConverter.ToInt32(bytes, 0);
            }
        }
        private static ThreadLocal<Random> m_rnd = new ThreadLocal<Random>(() => new Random(GetCryptoRandom()));
        private static Random _rnd
        {
            get
            {
                return m_rnd.Value;
            }
        }
        static void Main(string[] args)
        {
            ConcurrentDictionary<int, int> dic = new ConcurrentDictionary<int, int>();
            Parallel.For(1, ITERATIONS, _ => dic.AddOrUpdate(_rnd.Next(1, RANDOM_MAX), 1, (k, v) => v + 1));
            foreach (var kv in dic)
                Console.WriteLine("{0} -> {1:0.00}%", kv.Key, ((double)kv.Value / ITERATIONS) * 100);
        }
    }
}

这在统计上似乎是正确的，结果范围从0.99%到1.01%。

Random不是线程安全的 - 您不得在未同步的情况下从多个线程使用相同的Random实例。

为什么你特别得到 1？好吧，Random的工作方式（在 4.5.2 中）是保留一个种子数组以及两个索引器。当您同时从多个线程使用它时，您的种子数组将变得一团糟，并且您几乎总是会在多个插槽中获得相同的值。基本操作执行类似 seed[a] - seed[b] 的操作，当这些值相同时，您会得到零。由于您要求最小值为 1，因此此 0 将移至 1 - 这就是您的异常。这在多核环境中发生得非常快，因为每次Next调用都会更新相当多的相互依赖状态。

有很多方法可以解决这个问题。一种是同步对公共Random实例的访问 - 但是，只有当您执行相对较少的随机操作时，它才有意义，在这种情况下，您无论如何都不会使用Parallel。如果性能是一个问题，则需要添加某种形式的预取（例如，批量、按线程或使用一些并发队列准备随机数），或使用其他方法。

另一种方法是为每个线程保留一个单独的Random实例。但是，这需要您仔细为每个实例选择一个种子，否则您的随机数最终可能会非常非随机。.NET 本身使用的方法（同样，使用 4.5.2 代码作为参考）是使用 Thread.CurrentThread.ManagedThreadId 作为种子，效果很好。另一种常见的方法是使用单个全局（同步）Random实例来初始化其他Random的种子，但根据您的要求，您可能需要确保不会生成重复的种子。

当然，您也可以使用其他一些随机数生成器。然而，伪随机生成器通常需要与Random相同的方法 - 它们严重依赖于它们的状态;这就是使它们首先成为伪随机的原因。加密生成器可能工作得更好，但这些生成器往往非常慢，并且无论如何都可能回退到同步方法，尤其是在没有硬件支持的情况下。

在某些情况下，根据一些合理的规则分配生成工作是有意义的。例如，如果您对游戏内资产使用伪随机程序生成，则以可重复的方式对不同生成器的种子设定明确规则可能是有意义的 - 当然，这也意味着您也不能真正使用Parallel，并且您必须更明确一点。

相关文章：