1

スレッドを使用してフィボナッチ数列のいくつかのインデックスに基づいて数値を再帰的に見つける必要があり、次のコードを試しましたが、プログラムが終了しません。何か足りないものがあれば教えてください。

コード：

  import java.math.BigInteger;
  import java.util.concurrent.*;

  public class MultiThreadedFib {

    private ExecutorService executorService;

    public MultiThreadedFib(final int numberOfThreads) {
      executorService = Executors.newFixedThreadPool(numberOfThreads);
    }

    public BigInteger getFibNumberAtIndex(final int index) 
      throws InterruptedException, ExecutionException {

      Future<BigInteger> indexMinusOne = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 1);
          }
      });

      Future<BigInteger> indexMinusTwo = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 2);
          }
      });

      return indexMinusOne.get().add(indexMinusTwo.get());
    }

    public BigInteger getNumber(final int index) 
    throws InterruptedException, ExecutionException {
      if (index == 0 || index == 1)
        return BigInteger.valueOf(index);

      return getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2));
    }
  }

修正しました（fiverに感謝します）

callメソッドからgetNumber（int）を呼び出す代わりに、そのインデックスの数値を計算する動的プログラミングアルゴリズムを呼び出しています。

そのためのコードは次のとおりです。

public class DynamicFib implements IFib {

private Map<Integer, BigInteger> memoize = new HashMap<Integer, BigInteger>();

public DynamicFib() {
  memoize.put(0, BigInteger.ZERO);
  memoize.put(1, BigInteger.ONE);
}

public BigInteger getFibNumberAtIndex(final int index) {

  if (!memoize.containsKey(index))
    memoize.put(index, getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2)));

  return memoize.get(index);
  }
}
4

3 に答える 3

1

あなたがしているのは、単純な再帰をスレッド/タスクを介した再帰に置き換えることです。

fib（0）とfib（1）のケースに到達するまで、各タスクはさらに2つのタスクを送信し、それらが完了するのを待ちます。待機中は、まだスレッドを使用しています。スレッドプールは制限されているため、すぐにsubmitブロックの呼び出しが行われるようになり、計算全体がロックされます。

それに加えてindexMinusTwo、計算が間違った答えを与えるというバグがあります。

しかし、それでも再帰的なマルチスレッドの手順は、メモ化された再帰的な非マルチスレッドの手順よりもはるかに時間がかかります。パフォーマンスを向上させるためのヒントはありますか？

上記の問題を「修正」したとしても（たとえば、無制限のスレッドプールを使用して）、メモ化を使用するシングルスレッドバージョンよりもパフォーマンスの高いマルチスレッドバージョンのフィボナッチを実行できる方法はありません。計算は、並列化には適していません。

于 2011-07-02T05:29:15.850 に答える
1

この再帰はスタックを非常に速くオーバーフローさせます。これは、より低いフィボナッチ数を何度も何度も計算しているためです-指数関数的に何度も。

これを回避する効果的な方法の1つは、メモ化された再帰を使用することです（動的計画法のアプローチ）。

基本的に、静的配列を使用して、すでに計算されたフィボナッチ数を保持します。必要な場合は、配列から取得します（すでに計算されている場合）。そうでない場合は、それを計算して配列に格納します。このようにして、各数値は1回だけ計算されます。

（もちろん、配列の代わりに他のデータ構造、つまりハッシュテーブルを使用できます）

于 2011-07-02T04:56:48.387 に答える
0

スレッドは、実行する独立したタスクがある場合に最適に機能します。定義上、フィボナッチ数列にはある程度の並列性はありません。各f（n）は、前の2つの値に依存します。そのため、複数のスレッドを使用して、1つを使用するよりも速くf（n）を計算することはできません（非効率的なアルゴリズムがない限り）

+潜在的に多数の操作を並列化できる唯一のことですが、これはa）複雑b）シングルスレッドソリューションよりも高速化するのが難しい可能性があります。

フィボナッチ数を計算する最も速く/最も簡単な方法は、1つのスレッドでループを使用することです。再帰を使用したり、値を記憶したりする必要はありません。

于 2011-07-02T14:05:45.300 に答える