java - 使用线程的斐波那契数列

Question

以下code尝试并行化斐波那契数问题。如何修改以限制线程数。

我知道斐波那契并不是线程的天然候选者。但想知道如何通过线程对其进行优化。

public class Fib extends Thread
{
    private int x;
    public int answer;

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

    public void run() {
        if( x <= 2 )
            answer = 1;
        else {
            try {
                Fib f1 = new Fib(x-1);
                Fib f2 = new Fib(x-2);
                f1.start();
                f2.start();
                f1.join();
                f2.join();
                answer = f1.answer + f2.answer;
            }
            catch(InterruptedException ex) { }
        }
    }

    public static void main(String[] args)
        throws Exception
    {
        try {
            Fib f = new Fib( Integer.parseInt(args[0]) );
            f.start();
            f.join();
            System.out.println(f.answer);
        }
        catch(Exception e) {
            System.out.println("usage: java Fib NUMBER");
        }
    }
}

Answer 1

将对 fib() 的每次调用分为两次调用效率低下 - 斐波那契数列的计算应在线性时间内完成。请参阅 this question 的答复.

也就是说，如果您仍然想使用线程，内存和/或使用 future 的结果是必不可少的。

<小时/>