仿真给出了正常 for 循环与并行 For 的不同结果

Question

当我尝试使用普通 for 循环（这是正确的结果）与 Parallel For 时，我对一个简单模拟示例的不同结果感到有点惊讶。请帮我找出可能是什么原因。我观察到，与正常情况相比，并行执行速度非常快。

using System;
using System.Collections.Generic;
using System.Threading.Tasks;

namespace Simulation
{
    class Program
    {

    static void Main(string[] args)
    {
       ParalelSimulation(); // result is .757056
       NormalSimulation();  // result is .508021 which is correct
        Console.ReadLine();
    }

    static void ParalelSimulation()
    {
        DateTime startTime = DateTime.Now;

        int trails = 1000000;
        int numberofpeople = 23;
        Random rnd = new Random();
        int matches = 0;

        Parallel.For(0, trails, i =>
            {
                var taken = new List<int>();
                for (int k = 0; k < numberofpeople; k++)
                {
                   var day = rnd.Next(1, 365);
                    if (taken.Contains(day))
                    {
                        matches += 1;
                        break;
                    }
                    taken.Add(day);
                }
            }
        );
        Console.WriteLine((Convert.ToDouble(matches) / trails).ToString());
        TimeSpan ts = DateTime.Now.Subtract(startTime);
        Console.WriteLine("Paralel Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds);
    }
    static void NormalSimulation()
    {
        DateTime startTime = DateTime.Now;

        int trails = 1000000;
        int numberofpeople = 23;
        Random rnd = new Random();
        int matches = 0;

        for (int j = 0; j < trails; j++)
        {
            var taken = new List<int>();
            for (int i = 0; i < numberofpeople; i++)
            {
               var day = rnd.Next(1, 365);
                if (taken.Contains(day))
                {
                    matches += 1;
                    break;
                }
                taken.Add(day);
            }
        }
        Console.WriteLine((Convert.ToDouble(matches) / trails).ToString());
        TimeSpan ts = DateTime.Now.Subtract(startTime);
        Console.WriteLine(" Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds);
    }
}

}

提前致谢

Answer 1

有几点：

1. Random 类不是线程安全的。每个工作线程需要一个新的 Random 实例。
2. 您正在以非线程安全的方式递增 matches 变量。您可能需要使用 Interlocked.Increment(ref matches) 来保证递增变量的线程安全。
3. 您的 for 循环和 Parallel::For 执行的次数不完全相同，因为您在 for 循环中执行了 <= 并且 Parallel::For 的第二个参数是独占，因此您需要在这种情况下将 1 添加到踪迹中以使它们相等。

试试这个：

static void ParalelSimulationNEW()
{
    DateTime startTime = DateTime.Now;

    int trails = 1000000;
    int numberofpeople = 23;
    int matches = 0;

    Parallel.For(0, trails + 1, _ =>
    {
        Random rnd = new Random();

        var taken = new List<int>();
        for(int k = 0; k < numberofpeople; k++)
        {
            var day = rnd.Next(1, 365);
            if(taken.Contains(day))
            {
                Interlocked.Increment(ref matches);
                break;
            }
            taken.Add(day);
        }
    });
    Console.WriteLine((Convert.ToDouble(matches) / trails).ToString());
    TimeSpan ts = DateTime.Now.Subtract(startTime);
    Console.WriteLine("Paralel Time Elapsed: {0} Seconds:MilliSeconds", ts.Seconds + ":" + ts.Milliseconds);
}

Answer 2

该代码包含关于比赛更新的数据竞赛。如果两个线程同时执行此操作，则两个线程都可以读取相同的值（例如 10），然后都将其递增（到 11）并将新值写回。因此，注册的匹配项将会减少（在我的示例中，是 11 个而不是 12 个）。解决方案是使用 System.Threading.Interlocked 对于这个变量。

我看到的其他问题：
- 串行循环包含 j 等于 trails 的迭代，而并行循环则不包含（结束索引在 Parallel.For);
- 类 Random 可能不是线程安全。

---

更新：我认为您无法通过 Drew Marsh 的代码得到您想要的结果，因为它没有提供足够的随机化。 每个 1M 实验都以完全相同的随机数开始，因为您使用默认种子启动 Random 的所有本地实例。本质上，您重复相同的实验 100 万次，因此结果仍然存在偏差。要解决这个问题，您需要每次为每个随机化器设置一个新值。 更新：我在这里并不完全正确，因为默认初始化使用系统时钟作为种子；然而，MSDN 警告说

由于时钟的分辨率有限，因此使用无参数构造函数连续创建不同的 Random 对象会创建产生相同随机数序列的随机数生成器。

因此，这仍然可能是随机化不足的原因，并且使用显式种子，您可能会得到更好的结果。例如，使用外循环迭代的次数进行初始化为我提供了一个很好的答案：

Parallel.For(0, trails + 1, j =>
{
    Random rnd = new Random(j); // initialized with different seed each time
    /* ... */          
});

但是，我注意到在 Random 的初始化移入循环后，所有加速都丢失了（在我的英特尔酷睿 i5 笔记本电脑）。由于我不是 C# 专家，所以我不知道为什么；但我认为类 Random 可能有一些由所有实例共享的数据，并且访问同步。

---

更新 2：使用 ThreadLocal为了在每个线程中保留一个 Random 实例，我获得了良好的准确性和合理的加速：

ThreadLocal<Random> ThreadRnd = new ThreadLocal<Random>(() =>
{
    return new Random(Thread.CurrentThread.GetHashCode());
});
Parallel.For(0, trails + 1, j =>
{
    Random rnd = ThreadRnd.Value;
    /* ... */          
});

请注意如何使用当前运行的实例的哈希码来初始化每个线程随机化器线程。