3

因此，我创建了以下方法来查找不超过某个数字的所有素数。关于如何加快速度的任何建议？

我这样称呼它；

interval = (value + NOOFTHREADS - 1) / NOOFTHREADS;
int max = interval * NOOFTHREADS;

tickets = new List<int>(NOOFTHREADS);
for (int i = 1; i <= NOOFTHREADS; i++)
{
    tickets.Add(i * (max / NOOFTHREADS));
}

Enumerable.Range(1, NOOFTHREADS)
.AsParallel()
.ForAll(_ => findPrimes());

带有一些全局变量；

static List<int> vals = new List<int>();
static List<int> tickets;
static int interval = new int();

以及方法；

public static void findPrimes()
    {
        int myTicket;
        lock (tickets)
        {
            myTicket = (int)tickets.Last();
            tickets.RemoveAt(tickets.Count - 1);
        }
        var max = myTicket;
        int min = max - interval +1;
        int num;

        var maxSquareRoot = Math.Sqrt(max);
        var eliminated = new System.Collections.BitArray(max + 1);
        eliminated[0] = true;
        eliminated[1] = true;
        for (int i = 2; i < (max) / 2; i++)
        {
            if (!eliminated[i])
            {
                if (i < maxSquareRoot)
                {
                    num = ((min + i -1 )/i)*i;

                    if (num == i)
                        num = num + i;

                    for (int j =num; j <= max; j += i)
                        eliminated[j] = true;
                }
            }
        }
        for (int b = (int)min; b < max; b++)
        {
            if (!eliminated[b])
                lock(vals)
                    vals.Add(b);
        }
    }
4

4 回答 4

5

Eratosthenes 的筛子可以很容易地并行化，您只需将其分成单独的块并单独筛选每个块。你已经开始了分裂，但还没有走得足够远以获得好的结果。让我们看看有什么问题findPrimes()

var max = myTicket;
int min = max - interval +1;
int num;

var maxSquareRoot = Math.Sqrt(max);
var eliminated = new System.Collections.BitArray(max + 1);

您为每个线程创建一个新BitArray线程，涵盖从 0 到 的所有数字max。对于筛选第一个块的线程来说，这很好，但对于后面的线程，您分配的内存比需要的多得多。使用较高的上限和许多线程，这本身就是一个问题，您(NOOFTHREADS + 1) * limit / 2在只limit需要大约位的地方大致分配了位。对于更少的线程和/或更低的限制，您仍然会恶化局部性并且会有更多的缓存未命中。

eliminated[0] = true;
eliminated[1] = true;
for (int i = 2; i < (max) / 2; i++)

您应该在i > maxSquareRoot. 然后循环体不再做任何有成效的事情，它只执行一次读取和一两次检查。每次迭代都不需要很长时间，但是如果是例如 10 11i ，那么对于所有from √maxtomax加起来都会这样做。仅对最后一个块执行此操作可能比单线程单块筛子花费更长的时间。max

{
    if (!eliminated[i])

eliminated[i]只能适用于i >= min(or i < 2)，这种情况只会在第一个块中遇到i <= maxSquareRoot（除非限制非常低）。所以对于其他块，你也消除了 4, 6, 8, 9, 10, 12, 14, ... 的倍数。很多浪费的工作。

    {
        if (i < maxSquareRoot)

在maxSquareRoot恰好是素数的情况下，您没有消除它的平方，比较应该是<=。

        {
            num = ((min + i -1 )/i)*i;

            if (num == i)
                num = num + i;

            for (int j =num; j <= max; j += i)
                eliminated[j] = true;
        }
    }
}

现在，当筛分完成后，你一步一步穿过大块的BitArray 

for (int b = (int)min; b < max; b++)
{
    if (!eliminated[b])
        lock(vals)
            vals.Add(b);
}

每当你找到一个素数时，你就会锁定列表vals并将素数添加到其中。如果有两个或更多线程几乎同时完成筛分，它们将在那里相互踩踏，锁定和等待将进一步减慢该过程。

为了减少空间使用，每个线程应该创建一个素数列表maxSquareRoot，并使用它来消除其块中的复合，以便BitArray只需要max - min + 1位。每个创建自己的列表的线程都会重复一些工作，但由于这里的上限很小，所以额外的工作并不多。我不知道如何处理并发读取访问，如果这不增加同步开销，您也可以只为所有线程使用一个列表，但我怀疑这会有所收获。

代码大致如下：

List<int> sievePrimes = simpleSieve(maxSquareRoot);
// simpleSieve is a standard SoE returning a list of primes not exceeding its argument
var sieve = new System.Collections.BitArray(max - min + 1);
int minSquareRoot = (int)Math.Sqrt(min);
foreach(int p in sievePrimes)
{
    int num = p > minSquareRoot ? p*p : ((min + p - 1)/p)*p;
    num -= min;
    for(; num <= max-min; num += p)
    {
        sieve[num] =true;
    }
}

现在，为了避免在将素数添加到列表时线程互相踩到脚趾，每个线程都应该创建自己的素数列表并在一个步骤中附加它（我不能 100% 确定这比添加每个素数更快它自己的锁，但如果不是我会感到惊讶）

List<int> primes = new List<int>();
for(int offset = 0; offset <= max-min; ++offset)
{
    if (!sieve[offset])
    {
        primes.Add(min + offset);
    }
}
lock(vals) vals.AddRange(primes);

（并且vals应该以大约预期素数数量的初始容量创建，以避免重新分配每个块）

于 2012-10-09T16:08:48.597 回答
0

是否有理由实施该教科书数学可读平方根算法？看看素数算法

于 2012-10-09T12:55:35.557 回答
0

已经有很多关于并行代码与串行代码性能的文档。Microsoft 建议您在将代码转换为使用并行架构之前阅读他们关于使用并行功能的文档。

考虑阅读此处发布的以下 Q/AI：

嵌套的 Parallel.ForEach 循环

.NET 中的性能分析

于 2012-10-09T13:23:13.587 回答
0

我认为你所有的锁都可能有问题，你应该尽量避免使用锁，它们非常昂贵。我不知道你算法的细节，但我认为你应该尝试以某种方式移除锁。票可以输入吗？他们可以有自己的输出队列，当所有完成后合并？

于 2012-10-09T13:39:25.863 回答