java - 多线程斐波那契

Question

public class Fibonacci {

public static class PFibo extends Thread {
    private int x;
    public long answer;

    public PFibo(int x) {
        this.x = x;
    }

    public void run() {
        if (x <= 2)
            answer = 1;
        else {
            try {
                PFibo t = new PFibo(x - 1);
                t.start();

                long y = RFibo(x - 2);

                t.join();
                answer = t.answer + y;

            } catch (InterruptedException ex) {
            }
        }
    }
}

public static long RFibo(int no) {
    if (no == 1 || no == 2) {
        return 1;
    }
    return RFibo(no - 1) + RFibo(no - 2);
}

public static void main(String[] args) throws Exception {
    try {
        long start = System.currentTimeMillis();
        PFibo f = new PFibo(30);
        f.start();
        f.join();
        long end = System.currentTimeMillis();
        System.out.println("Parallel-Fibonacci:" + f.answer + "\tTime:" + (end - start));

        start = System.currentTimeMillis();
        long result = RFibo(30);
        end = System.currentTimeMillis();
        System.out.println("Normal-Fibonacci:" + result + "\tTime:" + (end - start));


    } catch (Exception e) {
    }
}

我目前正在阅读“算法导论”中的“多线程算法”。我尝试实现一个基本的多线程程序来计算第 n 个斐波那契数。对于 n=30，程序给出以下输出:

Parallel-Fibonacci:832040   Time:10
Normal-Fibonacci:832040     Time:3

为什么并行版本比非并行版本慢。线程切换或“太多线程”是否减慢了速度？

必须遵循什么方法来加速并行版本？

Answer 1

Has thread-switching or 'too-many-number-of-threads' slowed it down ?

当然可以。在许多方面——
正如评论中已经指出的那样

1. 您正在为每次调用创建一个新线程，即
   PFibo t = new PFibo(x - 1); t.start();

实际上，您已经为 PFibo(30) 创建了大约 28 个线程，这意味着一个上下文切换来评估每个术语

1. 其次，由于 PFibo(x) 的计算取决于 PFibo(x - 1)，它要求您在其中调用 join() 方法，因此每次您创建/启动一个新线程，即最终它变成了连续线程。
   

因此，最终成本 = 实际串行方法的成本 RFibo(n) + 大约 n 次上下文切换 + 同步时间(join())

What approach has to followed to speed-up the parallel version ?

好吧，我会说，不要这样做。斐波那契数列的解决方案模式不适合并行优化。仅依赖串行版本(您可以实现迭代版本以提高效率)。