C# Threaded Eratosthene 误解

Question

我有两个使用埃拉托色尼筛法生成素数的函数，一个使用简单循环，另一个使用任务在多个线程上进行运行计算。

因为我需要在使用线程时锁定值列表，所以我假设线程版本不会比普通版本快。但是经过一些测试，普通版似乎比线程版差了大约6倍。

更奇怪的是，一次只使用一个任务时，它比普通版本快 6 倍。我错过了什么？

代码如下：

    public static List<int> UsualPrimesGenerator(int n)
        {
            if (n < 0)
                return new List<int>();
            List<int> res = new List<int>();
            for (int i = 2; i < n; i++) res.Add(i);

            for (int i = 2; i * 2 <= n; i++)
            {
                res.RemoveAll(p => p != i && p % i == 0);
            }

            return res;
        }

        public static List<int> MagicPrimesGenerator(int n, int nbTasks)
        {
            if (nbTasks <= 0)
                throw new ArgumentException("Nbthread must be positive");

            var threads = new Task[nbTasks];

            List<int> primes = new List<int>();
            for (int i = 2; i <= n; i++)
                primes.Add(i);

            for (int i = 2; i * 2 <= primes.Count; i++)
            {
                if (threads[i % nbTasks] == null)
                {
                    var i2 = i;
                    threads[i % nbTasks] = Task.Run(() =>
                    {
                        lock (primes)
                        {
                            primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        }
                    });
                }
                else
                {
                    threads[i % nbTasks].Wait();
                    var i2 = i;
                    threads[i % nbTasks] = Task.Run(() =>
                    {
                        lock (primes)
                        {
                            primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        }
                    });
                }
            }

            for (int i = 0; i < nbTasks; i++)
            {
                if (threads[i] != null)
                    threads[i].Wait();
            }

            return primes;
        }

n = 100000 的时间测试结果：

Usual Prime Generator: 2732ms
9592 Primes found
Magic Prime Generator: 397ms
9592 Primes found

Answer 1

存在差异的原因是您在简单的解决方案中进行了更多的迭代。如果您将循环更改为：

for (int i = 2; i * 2 <= n; i++)
{
    res.RemoveAll(p => p != i && p % i == 0);
}

利用rs.count - 那么它的行为就像魔术方法一样。

for (int i = 2; i * 2 <= res.count; i++)
{
    res.RemoveAll(p => p != i && p % i == 0);
}

我没有检查正确性，但我想这不是你的问题。也，您的测量方法可以按照上面的评论中提到的进行改进。但这不是本例的问题。

循环中带有计数器的完整代码。

class Program
{
    private const int n = 100000;
    
    static void Main(string[] args)
    {
        MagicPrimesGenerator(n, 12);
        MagicPrimesGenerator(n, 12);
        MagicPrimesGenerator(n, 12);
        MagicPrimesGenerator(n, 12);
        UsualPrimesGenerator(n);
        UsualPrimesGenerator(n);
        UsualPrimesGenerator(n);
        UsualPrimesGenerator(n);
        
        var sw = new Stopwatch();
        sw.Start();

        sw.Reset();
        sw.Start();
        MagicPrimesGenerator(n, 1);
        Console.WriteLine($"B: Magic Prime Generator: {sw.ElapsedMilliseconds} ms");
        
        sw.Reset();
        sw.Start();
        UsualPrimesGenerator(n);
        Console.WriteLine($"A: Usual Prime Generator: {sw.ElapsedMilliseconds} ms");
    }
    
    
    public static List<int> UsualPrimesGenerator(int n)
    {
        int count = 0;
        if (n < 0)
            return new List<int>();
        List<int> res = new List<int>();
        for (int i = 2; i < n; i++) res.Add(i);

        for (int i = 2; i * 2 <= res.Count; i++)
        {   
            res.RemoveAll(p => p != i && p % i == 0);
            count++;
        }
        
        Console.Write("usual iteration count ");
        Console.WriteLine(count);
        return res;
    }

    public static List<int> MagicPrimesGenerator(int n, int nbTasks)
    {
        if (nbTasks <= 0)
            throw new ArgumentException("Nbthread must be positive");

        var threads = new Task[nbTasks];
        int count = 0;

        List<int> primes = new List<int>();
        for (int i = 2; i <= n; i++)
            primes.Add(i);

        for (int i = 2; i * 2 <= primes.Count; i++)
        {
            if (threads[i % nbTasks] == null)
            {
                var i2 = i;
                threads[i % nbTasks] = Task.Run(() =>
                {
                    lock (primes)
                    {
                        primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        count++;
                    }
                });
            }
            else
            {
                threads[i % nbTasks].Wait();
                var i2 = i;
                threads[i % nbTasks] = Task.Run(() =>
                {
                    lock (primes)
                    {
                        primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        count++;
                    }
                });
            }
        }

        for (int i = 0; i < nbTasks; i++)
        {
            if (threads[i] != null)
                threads[i].Wait();
        }
        
        Console.Write("magic iteration count ");
        Console.WriteLine(count);

        return primes;
    }
}

C# Threaded Eratosthene 误解

C# Threaded Eratosthene misunderstanding

c#

primes

multithreading