平行斐波那契数计算器 [英] Parallel Fibonacci Number Calculator

问题描述

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

 公共静态int Fib(int n){如果(n< = 1){返回n;}任务< int>任务= Task.Factory.StartNew< int>((()=> Fib(n-1));var p = Fib(n-2);返回task.Result + p;}公共静态无效的Main(string [] args){秒表手表=新的秒表();watch.Start();Console.WriteLine("Answer:" + Fib(44));watch.Stop();Console.WriteLine("Time:" + watch.ElapsedMilliseconds);}} 

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

 公共类FibTester{公共静态int Fib(int n){如果(n< = 1){返回n;}var q = Fib(n-1);var p = Fib(n-2);返回p + q;}公共静态无效的Main(string [] args){秒表手表=新的秒表();watch.Start();Console.WriteLine("Answer:" + Fib(44));watch.Stop();Console.WriteLine("Time:" + watch.ElapsedMilliseconds);}} 

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

解决方案

这是如何不进行多线程的完美示例！

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

每个线程有两个工作:1-创建一个新线程，2-加两个数字.

创建每个线程的开销费用将远远超过将两个数相加的开销.

---

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

I'm using Task Parallel Library (TPL ) for calculating Fibonacci number. Program is given below:

        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);
        }
    }

Unfortunately this program takes a very long time to complete. But serial version of this program ( as given below ) takes less than 30 seconds to calculate 44th Fibonacci number.

 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);
        }
    }

I think issue in parallel version is, it creates a thread for each Fib(n - 1) request. Is there any way to control number of thread created in TPL?

解决方案

This is a perfect example of how not to multithread!

You are creating a new task for each iteration of a recursive function. So each task creates a new task, waits for that task to finish and then adds the numbers from the result.

Each thread has two jobs : 1 - to create a new thread, 2 - to add two numbers.

The overhead cost for creating each thread is going to far outweigh the cost of adding two numbers together.

---

To answer your question about limiting the number of threads created, the TPL uses the ThreadPool. You can limit the number of threads using ThreadPool.SetMaxThreads.

这篇关于平行斐波那契数计算器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！