我有可能使用PLINQ挤出任何额外的效率吗? [英] Is it possible for me to squeeze out any extra efficiency using PLINQ?

问题描述

我正在尝试解决一个问题，即找到给定范围内的所有质数，其每个数字也是质数.

I'm trying to solve a problem that is to find all the prime numbers in a given range whose every digit is also prime.

例如在[1, 100]范围内的答案是8，因为2, 3, 5, 7, 23, 37, 53, 37是满足该条件的所有数字.

e.g. in the range [1, 100] the answer is 8 because 2, 3, 5, 7, 23, 37, 53, 37 are all the numbers satisfying it.

我当前的解决方案是正确的

My current solution is correct

// Yields all the numbers in the range [start, end] that could be primes,
// by taking into account the fact that a prime is either 2, 3, 6k + 1 or 6k - 1
static IEnumerable<long> PossiblePrimeNumbers(long start, long end)
{
    if(start <= 2 && end >= 2)
        yield return 2;
    if(start <= 3 && end >= 3)
        yield return 3;
    for(long n = (start / 6 + 1) * 6; ; n += 6)
    {
        if((n - 1) <= end)
            yield return (n - 1);
        if((n + 1) <= end)
            yield return (n + 1);
        else break;
    }
}

// Map for fast checking of whether a digit 0, 1, ..., 9 is a prime
static bool[] IsPrimeDigit = { false, false, true, true, false, true, false, true, false, false };

// True or false depending on whether m is prime
static bool IsPrime(long m)
{
    long boundary = (long)Math.Floor(Math.Sqrt(m));

    bool isPrime = true;

    for(long i = 2; i <= boundary; ++i)
    {
        if(m % i == 0)
        {
            isPrime = false;
            break;
        }
    }

    return isPrime;
}

// True or false depending on whether all the digits of m are prime and
// whether m itself is prime
static bool IsMegaprime(long m)
{
    return m.ToString().All(c => IsPrimeDigit[c - '0']) && IsPrime(m);
}

// Counts the number of "megaprimes" (defined above) in the range [first, last]
static int NumberMegaprimes(long first, long last)
{
    return PossiblePrimeNumbers(first, last).AsParallel().Count(m => IsMegaprime(m));
}

static void Main(String[] args)
{
    long first = 1;
    long last = 100;
    Console.WriteLine(NumberMegaprimes(first, last)); // should print 8
}

，您甚至可以看到我添加了.AsParallel()来尝试加快速度.

and you can even see that I've added an .AsParallel() to try and speed it up.

有什么明显的方法可以加快速度吗? (除了摆脱LINQ)

Are there any obvious ways to speed this up? (Other than getting rid of LINQ)

推荐答案

如果使用AsParallel()，您的CPU达到了100％的上限，那么-考虑到您是否可以挤出额外的效率的精神的答案是不".CPU已成为您的瓶颈，您的选择要么是获得更好的CPU，要么是使用更好的算法.

If with AsParallel() your CPU is hitting the 100% ceiling then - in the spirit of the question of whether you can squeeze out extra efficiency out of PLINQ - the short answer is No. The CPU has become your bottleneck, and your options are either to get a better CPU, or to use a better algorithm.

如萨米(Sami)的评论所述，要获得算法帮助，最好在 CodeReview 中进行询问.

As Sami's comment mentioned, for help with algorithms you're better off asking in CodeReview.

这篇关于我有可能使用PLINQ挤出任何额外的效率吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！