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을 구현합니다. 아시다시피, 제 교수님의 운동입니다.

자바에서 스레드를 시작하는 방법을 알고 있고이 전체 스레드가 이론적으로 어떻게 작동하는지 알고 있지만이 재귀 함수에서 별도의 스레드를 시작하기위한 솔루션을 찾을 수 없습니다.

실행 기능에서 수행해야 할 작업은 무엇입니까?

아마

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(); 

에서

또는 완전히 잘못된 경로 I입니까?

Answer 1

이 작업을하려면 1) 새 스레드에 숫자를 전달하는 방법, 2) 스레드를 시작하는 방법, 3) 스레드가 완료 될 때까지 기다리는 방법, 4) 결과를 얻는 방법이 필요합니다. 다시 스레드에서.

생성자를 통해 번호를 전달할 수 있습니다. 계산 결과를 포함하는 "응답"이라는 공개 데이터 멤버를 가질 수 있습니다. 스레드를 시작하는 것은 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

당신은, 생성자를 통해 객체에 x 전달에 대해 fib 기능 스레드를 시작하는 방법에 대한 올바른 생각을 가지고; 당신은 또한 결국 객체의 계산 결과를 얻을 수있는 방법이 필요합니다 - 당신이 그것을 알아낼 수 있다고 확신합니다 ;-) fib에서 사용하는 스레드 시작 프로 시저는 똑같은 방법입니다 (new Fib(x-1)).start()과 같은 스레드를 항상 시작합니다. 나중에 계산 결과를 얻기 위해 스레드를 변수에 저장하려고 할 수 있습니다.

Answer 3

스레드 사용은 일반적으로 성능을 향상시키기위한 것입니다. 그러나 각 스레드는 오버 헤드를 추가하고 수행되는 작업이 작 으면 실제 수행되는 작업보다 훨씬 많은 작업이있을 수 있습니다. 또한 대부분의 PC는 약 1000 개의 스레드 만 처리 할 수 ​​있으며 10K 개가 넘는 스레드가있는 경우 중단됩니다.

fib (20)은 6765 개의 스레드를 생성하고 fib (30)은 832K를 생성하고 fib (40)은 102,000 개의 스레드를 생성하며 fib (50)은 12 조 개가 넘는 스레드를 생성합니다. 이 확장 성이 없다는 것을 알기를 바랍니다.

그러나 다른 방법을 사용하면 1 분 이내에 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 4

여러분 모두의 도움으로 스레드 클래스를 사용하는 대신 runnable을 구현할 때 동일한 작업을 수행했습니다.

만약 당신이 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"); 
    } 
    } 
}