フィボナッチスレッドを使用

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

現在の数のスレッド/スレッドのポーリングまたはsmt elseを含むスレッド用のファクトリを作成できます。このファクトリの主な問題はスレッドの作成です。

Answer 2

fib（）の呼び出しを2回の呼び出しに分岐するのは非効率的です。フィボナッチ系列の計算は、線形時間で行う必要があります。 this questionへの回答を参照してください。

それでも、スレッドを使用したい場合は、メモ化や今後の結果の使用が不可欠です。

---

Answer 3

フィボナッチは、しかし、それはおそらく、一つのスレッドが高速である使用した場合の最良の例で注意しなければならないその簡単に理解し、宿題のためにそれが良いになりどの実装するためのスレッドの多くを作成するための一般的な例であります複数のスレッドを使用しようとするよりも、その理由は、多くのスレッドを持つことによるオーバーヘッドが指数関数的に増加する結果に比例するということです。

つまり、最適なスレッド数は1です。一度それを知って、あなたのコードははるかに簡単になります。

コードを最適化したい場合は、ループの最初の値から値を構築する必要があります。つまり、1,1,1,2,3,5,8 ...で始まります。これにより、指数関数的に行う呼び出しの数も減ります。