Java中使用线程和递归计算斐波那契数的多线程处理

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中启动线程，我也知道整个线程在理论上是如何工作的，但是我找不到一个解决方案来在这个递归函数中启动单独的线程

在run函数中必须做什么

大概

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

如何在我的可运行函数中粘贴x？ x是否在创建时传递到对象中

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

}

主要方法

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

还是我走错了路

Answer 1

关于在fib函数中启动线程，以及通过构造函数将x传递给对象，您的想法是正确的；您还需要有一种方法在最后从对象中获得计算结果-我相信您可以计算出来；-）在fib中使用的线程启动过程与始终启动线程的方式相同，如(new Fib(x-1)).start()尽管您可能希望将线程保存在变量中，因为以后需要它来获得计算结果

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

Answer 3

所以在大家的帮助下，我实现了runnable，而不是使用Thread类

请大家看一看，并告诉我，如果任务是实现runnable，那么这是如何实现的。 代码本身是有效的

public class Fib implements Runnable
{
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);
            Thread threadf1=new Thread(f1);
            Thread threadf2=new Thread(f2);
            threadf1.start();
            threadf2.start();
            threadf1.join();
            threadf2.join();

            answer = f1.answer + f2.answer;

        }
        catch(InterruptedException ex) { }
    }
}

public static void main(String[] args)

{
    try {

            for (int i=0;i<19;i++){
                Fib f= new Fib(i);
                Thread threadf= new Thread(f);
                threadf.start();
                threadf.join();

                System.out.println("Ergebnis:"+f.answer);

            }
        }

    catch(Exception e) {
        System.out.println("usage: java Fib NUMBER");
    }
  }
}