在Java中使用线程和递归来计算Fibonacci数

Question

我在Java世界中比较新,我有一个我不明白的问题.

我有一个类(获得斐波纳契行):

class Fib {
    public static int f(int x){
        if ( x < 2 )
            return 1;       
        else 
            return f(x-1)+ f(x-2);      
    }
}

现在的任务是在一个单独的线程中启动f(x-1)和f(x-2).一次实现Thread类,另一次实现Runnable.你可能知道,这是我教授的练习.

我知道如何在Java中启动一个Thread,我知道整个Thread事物在理论上是如何工作的,但我找不到在这个递归函数中启动单独Threads的解决方案.

在run函数中需要做什么？

大概

public void run(){
//int foo=start f(this.x-1)
    //int bar=start f(this.x-2)  
    //return foo+bar?
}

如何在我的runnable函数中粘贴x？x是否在创建时传递给对象？

Class Fib ...{
  int x;
  public ... run ... 
  public ... f(x)....

}

在主要方法

(new Fib(x)).start();

还是我走错了路？

Answer 1

为此,你需要1)一种方法将数字传递给新线程,2)启动线程,3)等待线程完成,以及4)从线程中获取结果的方法.

您可以通过构造函数传递数字.您可以拥有一个名为"answer"的公共数据成员来包含计算结果.可以使用该start()方法启动线程,并且该join()方法等待线程完成.

以下示例演示了这一点.这应该是一个很好的起点; 从这里你可以抽象出一些混乱,以获得更好的API.

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 2

使用线程通常旨在提高性能.但是,每个线程都会增加开销,如果执行的任务很小,那么可能会比实际完成的工作多得多.此外,大多数PC只能处理大约1000个线程,如果你的线程超过10K,它们就会挂起.

在你的情况下,fib(20)将产生6765个线程,fib(30)产生832K,fib(40)产生102M线程,fib(50)产生超过12万亿个线程.我希望你能看到这是不可扩展的.

但是,使用不同的方法,您可以在一分钟内计算fib(1000000).

import java.math.BigInteger;

/*
250000th fib # is: 36356117010939561826426 .... 10243516470957309231046875
Time to compute: 3.466557 seconds.
1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875
Time to compute: 58.1 seconds.
*/
public class Main {
    public static void main(String... args) {
        int place = args.length > 0 ? Integer.parseInt(args[0]) : 250 * 1000;
        long start = System.nanoTime();
        BigInteger fibNumber = fib(place);
        long time = System.nanoTime() - start;

        System.out.println(place + "th fib # is: " + fibNumber);
        System.out.printf("Time to compute: %5.1f seconds.%n", time / 1.0e9);
    }

    private static BigInteger fib(int place) {
        BigInteger a = new BigInteger("0");
        BigInteger b = new BigInteger("1");
        while (place-- > 1) {
            BigInteger t = b;
            b = a.add(b);
            a = t;
        }
        return b;
    }
}