1

static List<long> primes在某个点之前，我有一个所有已知的素数，以及这样的函数：

static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    foreach (long q in primes)
    {
        if (p % q == 0)
            return false;

        if (q >= rootP)
            return true;
    }

    return true;
}

可以这样并行化：

static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    primes.AsParallel().ForAll(q =>
        {
            if (p % q == 0)
                return false;

            if (q > rootP)
                break;
        });

    return true;
}

但是，这会产生一个编译时错误，说明我的块中的某些返回类型不能隐式转换为委托返回类型。

我对 LINQ 有点陌生，尤其是 PLINQ。对我来说，这似乎是并行性的一个很好的候选，因为每个已知素数与候选素数的检查是一个独立的过程。

有没有一种简单的方法可以修复我的块以使其正常工作，还是我需要以完全不同的方式解决这个问题？

4

4 回答 4

1

This is a solution to your problem:

static List<long> primes = new List<long>() {
  2,3,5,7,11,13,17,19,23
};

static bool isPrime(long p) {
  var sqrt = (long)Math.Sqrt(p);
  if (sqrt * sqrt == p)
    return (false);
  return (primes.AsParallel().All(n => n > sqrt || p % n != 0));
}

It even tries to reduce parallelism for quadratic numbers and will stop checking more candidates as soon as the first is found which is

于 2013-05-30T07:39:38.553 回答
1

在语法方面，您在代码中犯了两个错误：

  1. lambda 中的Areturn不会从封闭方法返回，而只是从 lambda 中返回，因此您return false;将无法正常工作。
  2. 你不能break离开 lambda。即使那个 lambda 在一个循环中执行，那个循环对你来说基本上是不可见的，你当然不能直接控制它。

我认为修复代码的最佳方法是使用专门为此目的制作的 LINQ 方法：Any()，同时TakeWhile()过滤掉太大的素数：

static bool IsPrime(long p)
{
    double rootP = Math.Sqrt(p);

    return !primes.AsParallel().TakeWhile(q => q > rootP).Any(q => p % q == 0);
}

但是你的推理也有一个缺陷：

对我来说，这似乎是并行性的一个很好的候选，因为每个已知素数与候选素数的检查是一个独立的过程。

这不是那么简单。检查每个素数也是一个极其简单的过程。这意味着简单并行化的开销（就像我上面建议的那样）可能大于性能提升。一个更复杂的解决方案（如 Matthew Watson 在评论中建议的解决方案）可以帮助解决这个问题。

于 2013-05-30T10:34:56.303 回答
0

改用 Parallel.For 可能更容易

static volatile bool result = true;
static bool isPrime(long p)
{
    double rootP = Math.Sqrt(p);

    Parallel.For(0, primes.Count, (q, state) =>
        {
            if (p % q == 0)
            {
                result = false;
                state.Break();
            }

            if (q > rootP)
                state.Break();
        });

    return result;
}
于 2013-05-30T11:01:15.037 回答
0

发生错误是因为如果您的情况

p % q == 0

是true关闭将返回false，何时

q > rootP

它打破并且什么也不返回。这将适用于 PHP，但不适用于 .NET：P

lambda 是一个完全匿名的函数，返回类型必须始终保持一致。

你必须在这里重新设计你的代码。你已经在你的非并行示例中做对了......只需替换break为return true（那时它不会更漂亮，但它应该可以工作）。

于 2013-05-30T06:47:02.350 回答