c# - 并行斐波那契数计算器

Question

我正在使用任务并行库 (TPL) 来计算斐波那契数。程序如下:

        public static int Fib(int n)
        {
            if (n <= 1)
            {
                return n;
            }
            Task<int> task = Task.Factory.StartNew<int>(() => Fib(n - 1));
            var p = Fib(n - 2);
            return task.Result + p;
        }

        public static void Main(string[] args)
        {

            Stopwatch watch = new Stopwatch();
            watch.Start();
            Console.WriteLine("Answer: " + Fib(44));
            watch.Stop();
            Console.WriteLine("Time: " + watch.ElapsedMilliseconds);
        }
    }

不幸的是，这个程序需要很长时间才能完成。但是这个程序的串行版本(如下所示)用时不到 30 秒计算第 44 个斐波那契数。

 public class FibTester
    {
        public static int Fib(int n)
        {
            if (n <= 1)
            {
                return n;
            }
            var q = Fib(n - 1);
            var p = Fib(n - 2);
            return p + q;
        }

        public static void Main(string[] args)
        {

            Stopwatch watch = new Stopwatch();
            watch.Start();
            Console.WriteLine("Answer: " + Fib(44));
            watch.Stop();
            Console.WriteLine("Time: " + watch.ElapsedMilliseconds);
        }
    }

我认为并行版本的问题是，它为每个 Fib(n - 1) 创建一个线程要求。有什么方法可以控制在 TPL 中创建的线程数吗？

Answer 1

这是如何不多线程的完美示例!

您正在为递归函数的每次迭代创建一个新任务。因此，每个任务都会创建一个新任务，等待该任务完成，然后将结果中的数字相加。

每个线程都有两个作业:1 - 创建一个新线程，2 - 添加两个数字。

创建每个线程的开销成本将远远超过将两个数字相加的成本。

---

为了回答有关限制创建的线程数的问题，TPL 使用了 ThreadPool。您可以使用 ThreadPool.SetMaxThreads 限制线程数.