平行斐波纳契数计算器

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个Fibonacci数.

 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限制线程数.