3

作为我的 BigDecimal 库的一部分，我需要计算任何给定非负整数的阶乘。所以我使用 .Net 4.0System.Numerics.BigInteger来存储大量数字。这是我正在使用的功能： 

private BigInteger Factorial(BigInteger x)
{
     BigInteger res = x;
     x--;
     while (x > 1)
     {
          res *= x;
          x--;
     }
     return res;
}

它可以工作，但没有优化。现在我想使用并行计算，所以这是我尝试过的：（我没有并行编程经验）

public BigInteger Factorial(long x)
{
     BigInteger res = 1;
     ParallelLoopResult r = Parallel.For(2L, (x + 1), i =>
          res *= i
     );
     return res;
}

奇怪的问题是，上面的函数非常适合像 5 这样的小数字！但不适用于像 1000 这样的大数字！并且每次返回完全不同的结果。所以我意识到它不是线程安全的，问题出在变量res上。我想知道正确的实现是什么？
如果我可以使用 BigInteger 而不是 long 作为 variable 会更好x。

4

3 回答 3

4

您需要确保您的并行进程不共享任何状态。

例如，在阶乘的情况下，我会执行以下操作：

  • 设置并行度 (DOP) - 通常是计算机上用于计算密集型操作的处理器数量
  • 将问题分成独立的子集
  • 并行处理每个子集
  • 汇总从并行过程中获得的结果

这在某种程度上是一个简化的Map-Reduce。

问题在于将一组数字相乘。将此集合划分为子集的一种方法是使用N并行 for 循环，其中每个循环都从一个值i(where 0 < i <= N) 开始，步长为N(and N= DOP)。

这是执行此操作的代码：

/// <summary>
/// The max number of parallel tasks
/// </summary>
static readonly int DegreeOfParallelism = Environment.ProcessorCount;

public BigInteger Factorial(long x)
{
    // Make as many parallel tasks as our DOP
    // And make them operate on separate subsets of data
    var parallelTasks =
        Enumerable.Range(1, DegreeOfParallelism)
                    .Select(i => Task.Factory.StartNew(() => Multiply(x, i),
                                 TaskCreationOptions.LongRunning))
                    .ToArray();

    // after all tasks are done...
    Task.WaitAll(parallelTasks);

    // ... take the partial results and multiply them together
    BigInteger finalResult = 1;

    foreach (var partialResult in parallelTasks.Select(t => t.Result))
    {
        finalResult *= partialResult;
    }

    return finalResult;
}

/// <summary>
/// Multiplies all the integers up to upperBound, with a step equal to DOP
/// starting from a different int
/// </summary>
/// <param name="upperBoud"></param>
/// <param name="startFrom"></param>
/// <returns></returns>
public BigInteger Multiply(long upperBound, int startFrom)
{
    BigInteger result = 1;

    for (var i = startFrom; i <= upperBound; i += DegreeOfParallelism)
        result *= i;

    return result;
}

在我的机器上，这个计算100000!大约需要 30 秒，结果就是Wolfram Alpha 所说的那样。

更新

在运行了几个测试之后，我发现了一些我没想到的东西：将100000!结果打印到控制台大约需要 18 秒（结果有456574数字）。

单独计算的结果100000!（不打印数字）是：

  • 并行执行约 10 秒
  • 约 16 秒顺序执行
于 2013-09-20T08:06:37.230 回答
3

前言

基于一些初始且非常简单的基准测试，并行版本对于非常大的阶乘（大于〜1000！）运行得更快。对于较小的版本，并行处理的开销胜过其他一切，而顺序版本的速度更快。

代码

话虽如此，这就是我在 LINQPad 中的工作：

public static class Math
{
    // Sequential execution
    public static System.Numerics.BigInteger Factorial(System.Numerics.BigInteger x)
    {
        System.Numerics.BigInteger res = x;
        x--;
        while (x > 1)
        {
            res *= x;
            x--;
        }
        return res;
    }
    
    public static System.Numerics.BigInteger FactorialPar(System.Numerics.BigInteger x)
    {
        return NextBigInt().TakeWhile(i => i <= x).AsParallel().Aggregate((acc, item) => acc * item);
    }
    
    public static IEnumerable<System.Numerics.BigInteger> NextBigInt()
    {
        System.Numerics.BigInteger x = 0;
        while(true)
        {
            yield return (++x);
        }
    }
}

这适用于小型（5！= 120、6！= 720）和大型（~8000！）阶乘。正如我所提到的，大型阶乘的速度提高（快 2 到 3 倍），但对于小型阶乘（在 LINQPad 中预热后的结果）会造成严重的性能损失（高达两个数量级）：

  • 6！x 20 -> Serial avg ticks/std dev: 4.2/2.014, Paralell avg ticks/std dev: 102.6/39.599 (并行执行慢 25 倍...)

  • 300！x 20 -> Serial avg ticks/std dev: 104.35, Parallel avg ticks/std dev: 405.55/175.44（并行运行为顺序的 1/4，速度明智）

  • 1000！x 20-> 串行 avg ticks/std dev: 2672.05/615.744, Parallel avg ticks/std dev: 3778.65/3197.308（并行运行在 ~70 - 90% 的连续速度）

  • 10000！x 20 -> 串行平均滴答数/标准开发：286774.95/13666.607，并行平均滴答/标准开发：144932.25/16671.931（并行快 2 倍）

拿那些持怀疑态度的人来说，您需要编译一个发布版本并将其作为独立版本运行以获得“真正的”结果，但那里有一个值得考虑的趋势。

10万！（打印和一切）在我的机器上用了 26 秒，在 LINQPad 中并行执行。

于 2013-09-20T08:15:34.623 回答
2

试试这个以获得更简单的解决方案：

Func<int, BigInteger> factorialAgg = n => n < 2 ? BigInteger.One 
                      : Enumerable.Range(2, n-1)
                        .AsParallel()
                        .Aggregate(BigInteger.One, (r, i) => r * i);

var result = factorialAgg(100000);
于 2016-11-10T13:22:14.633 回答