在 Java 中使用线程和递归来计算斐波那契数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/706048/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using threads and recursion in Java to calculate Fibonacci numbers
提问by evildead
I'm relatively new in the Java world and I have a problem which I don't understand.
我在 Java 世界中相对较新，我有一个我不明白的问题。
I have a Class (to get the fibonacci row):
我有一个类（获取斐波那契行）：
class Fib {
public static int f(int x){
if ( x < 2 )
return 1;
else
return f(x-1)+ f(x-2);
}
}
The task now is to start f(x-1) and f(x-2) each in a separate Thread. One time with implementing the Thread class and the other with implementing Runnable. As you probably know, it's an exercise from my prof.
现在的任务是在单独的线程中分别启动 f(x-1) 和 f(x-2)。一次是实现 Thread 类，另一次是实现 Runnable。您可能知道，这是我教授的练习。
I know how to start a Thread in Java and I know how this whole Thread thing theoretically works, but I can't find a solution for starting separate Threads in this recursive function.
我知道如何在 Java 中启动一个线程，并且我知道整个 Thread 的事情理论上是如何工作的，但是我找不到在这个递归函数中启动单独线程的解决方案。
What has to be done in the run function?
在 run 函数中必须做什么？
Probably
大概
public void run(){
//int foo=start f(this.x-1)
//int bar=start f(this.x-2)
//return foo+bar?
}
And how can I paste x in my runnable function? Is x passed into the object at creation?
以及如何将 x 粘贴到我的可运行函数中？x 是否在创建时传入对象？
Class Fib ...{
int x;
public ... run ...
public ... f(x)....
}
in the main method
在主方法中
(new Fib(x)).start();
Or am I on a totally wrong path?
还是我走上了完全错误的道路？
采纳答案by Eli Courtwright
For this to work, you need 1) a way to pass the number into the new thread, 2) to start the thread, 3) to wait for the thread to finish, and 4) a way to get the result back from the thread.
为此，您需要 1) 将数字传递给新线程的方法，2) 启动线程，3) 等待线程完成，以及 4) 从线程获取结果的方法.
You can pass in the number through the constructor. You can have a public data member called "answer" to contain the result of the computation. Starting the thread can be done with the start()method, and the join()method waits for the thread to complete.
您可以通过构造函数传入数字。您可以使用名为“answer”的公共数据成员来包含计算结果。启动线程可以通过start()方法完成，join()方法等待线程完成。
The following example demonstrates this. That should be a good starting point; from here you can abstract away some of the messiness to get a better API as desired.
以下示例演示了这一点。这应该是一个很好的起点；从这里您可以抽象出一些混乱以获得所需的更好的 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");
}
}
}
回答by David Z
You've got the right idea about starting threads in the fibfunction, and about passing xto the object through the constructor; you'll also need to have a way to get the result of the calculation out of the object at the end - I'm sure you can figure that out ;-) The thread-starting procedure you use in fibis just the same way you always start a thread, like (new Fib(x-1)).start()although you might want to save the thread in a variable because you'll need it to get the result of the computation later.
您对在fib函数中启动线程以及x通过构造函数传递给对象有正确的想法；您还需要有一种方法在最后从对象中获取计算结果 - 我相信您可以弄清楚;-) 您使用的线程启动过程与您使用fib的方式相同总是启动一个线程，就像(new Fib(x-1)).start()虽然您可能想将线程保存在一个变量中，因为稍后您将需要它来获取计算结果。
回答by Peter Lawrey
Using threads is usually intended to improve performance. However each thread adds an overhead and if the task performed is small, there can be much more over head than actual work done. Additionally most PCs can only handle about 1000 threads and will hang if you have much more than 10K threads.
使用线程通常是为了提高性能。然而，每个线程都会增加开销，如果执行的任务很小，则开销可能比实际完成的工作多得多。此外，大多数 PC 只能处理大约 1000 个线程，并且如果线程数超过 10K，就会挂起。
In your case, fib(20) will generate 6765 threads, fib(30) creates 832K, fib(40) creates 102M threads, fib(50) creates over 12 trillion. I hope you can see this is not scalable.
在您的情况下，fib(20) 将生成 6765 个线程，fib(30) 创建 832K，fib(40) 创建 102M 个线程，fib(50) 创建超过 12 万亿。我希望你能看到这是不可扩展的。
However, using a different approach you can calculate fib(1000000) in under one minute.
但是，使用不同的方法，您可以在一分钟内计算 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;
}
}
回答by evildead
So with the help of you all I managed to do the same thing with implementing runnable instead of using the Thread Class.
所以在你们所有人的帮助下，我设法通过实现 runnable 而不是使用 Thread 类来做同样的事情。
Can you all have a look and tell me if thats the way how to do it if the task is to implement runnable. The Code itself works.
你们都可以看看并告诉我如果任务是实现可运行的，这是否是如何做到的。守则本身有效。
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");
}
}
}
