Параллельный калькулятор числа Фибоначчи

Question

Я использую Task Parallel Library (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 .

Answer 2

Я думаю, что довольно ясно, что Фибоначчи нельзя распараллелить, если вы заранее не знаете несколько пар смежных чисел Фибоначчи

Просто перейдите к итеративному коду.

Что бы вы ни делали, не создавайте Task / Thread на каждой итерации / рекурсии! Накладные расходы убьют производительность. Это большой жирный анти-паттерн, даже если применяется распараллеливание.

Answer 3

Просто для удовольствия:)

using System;
using System.Linq;
using System.Threading.Tasks;

public class Program
{
    static readonly double sqrt5 = Math.Sqrt(5);
    static readonly double p1 = (1 + sqrt5) / 2;
    static readonly double p2 = -1 * (p1 - 1);

    static ulong Fib1(int n) // surprisingly slightly slower than Fib2
    {
        double n1 = Math.Pow(p1, n+1);
        double n2 = Math.Pow(p2, n+1);
        return (ulong)((n1-n2)/sqrt5);
    }

    static ulong Fib2(int n) // 40x faster than Fib3
    {
        double n1 = 1.0;
        double n2 = 1.0;
        for (int i=0; i<n+1; i++)
        {
            n1*=p1;
            n2*=p2;
        }
        return (ulong)((n1-n2)/sqrt5);
    }

    static ulong Fib3(int n) // that's fast! Done in 1.32s
    {
        double n1 = 1.0;
        double n2 = 1.0;
        Parallel.For(0,n+1,(x)=> {
            n1 *= p1; 
            n2 *= p2; 
        });
        return (ulong)((n1-n2)/sqrt5);
    }

    public static void Main(string[] args)
    {
        for (int j=0; j<100000; j++)
            for (int i=0; i<90; i++)
                Fib1(i);
        for (int i=0; i<90; i++)
            Console.WriteLine(Fib1(i));
    }
}

Answer 4

Ваша программа очень неэффективна, потому что одни и те же вычисления повторяются (Fib (n-1) фактически пересчитывает число Fib для всех чисел

Вы должны попробоватьэто:

class Program
{
    static void Main(string[] args)
    {
        var sw = new Stopwatch();
        sw.Start();
        foreach (var nbr in Fibo().Take(5000))
        {
            Console.Write(nbr.ToString() + " ");
        }
        sw.Stop();
        Console.WriteLine();
        Console.WriteLine("Ellapsed : " + sw.Elapsed.ToString());
        Console.ReadLine();
    }

    static IEnumerable<long> Fibo()
    {
        long a = 0;
        long b = 1;
        long t;

        while (true)
        {
            t = a + b;
            yield return t;
            a = b;
            b = t;
        }
    }
}

44-й поиск в 5 мс.

Самая медленная часть кода - Console.Write в цикле.