Java ExecutorService解決遞歸斐波那契數列

我需要根據Fibonacci Series中的一些索引來遞歸地使用線程找出數字，並且我嘗試了下面的代碼，但程序永遠不會結束。請讓我知道如果我失去了一些東西。Java ExecutorService解決遞歸斐波那契數列

代碼：

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

固定它（感謝晚五）

而是來自呼叫方法調用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); 
    } 
}

來源

2011-07-02 Shankar

這遞歸會溢出堆棧非常快。這是因爲你一次又一次地計算更低的斐波那契數 - 成倍數倍。

避免的一個有效方法是使用memoized遞歸（動態規劃方法）

基本上使用靜態數組來保存已經計算斐波那契數，只要你需要一個，把它從數組，如果它已經被計算出來了。如果不是，則計算它並將其存儲在數組中。這樣每個數字將只計算一次。

（您可以使用其他數據結構，而不是陣列，當然，即哈希表）

來源

2011-07-02 04:56:48

得到它的工作！謝謝！ :) – Shankar

但仍然遞歸多線程過程比memoized遞歸非多線程一個..任何提示，以提高性能？ – Shankar

好吧，這就是要點 - 簡單的遞歸永遠不會結束（甚至是多線程的），因爲迭代的次數會成倍增長 –

什麼，你正在做的是通過螺紋/任務遞歸取代簡單的遞歸。

在你到達fib（0）和fib（1）的情況下，每個任務都會提交兩個任務，然後等待它們完成。在等待時，它仍在使用線程。由於線程池是有界的，您很快就會到達調用submit的地方，並且整個計算都會鎖定。

除此之外，你有在indexMinusTwo一個錯誤，這會導致計算給出錯誤的答案。

但還是遞歸多線程程序所需的時間比memoized遞歸非多線程一個更長的時間..任何提示，以提高性能？

即使假設你「固定」的上述問題（例如，通過使用無界線程池）有沒有辦法，你就可以做一個多線程版本的斐波那契的執行比一個更好的使用記憶的單線程版本。這個計算根本不適合並行化。

來源

2011-07-02 05:29:15

謝謝你的澄清。不過，請讓我知道該代碼中的錯誤究竟在哪裏 – Shankar

您已修復它。 –

當您有獨立的任務執行時，線程效果最佳。根據定義，斐波那契數列沒有任何平行度。每個f（n）取決於前兩個值。因此，使用多線程計算f（n）的速度不可能比使用多線程計算的速度快（除非您的算法效率低）

您可以爲大數製作並行潛在的+操作，但這很可能成爲a）複雜b）難以比單線程解決方案做得更快。

計算斐波那契數的最快/最簡單的方法是在一個線程中使用循環。您不需要使用recusrion或記憶值。

來源

2011-07-02 14:05:45

Java ExecutorService解決遞歸斐波那契數列

回答

相關問題