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) 的情况之前，每个任务都会再提交两个任务，然后等待它们完成。在等待时，它仍在使用线程。submit由于线程池是有界的，您很快就会到达调用block ... 并且整个计算锁定的地步。

除此之外，您还有一个错误indexMinusTwo，会导致计算给出错误的答案。

但是递归多线程过程仍然比记忆的递归非多线程过程花费更长的时间。有什么提高性能的技巧吗？

即使假设您“修复”了上述问题（例如，通过使用无界线程池） ，您也无法执行比使用 memoization 的单线程版本更好的多线程版本的斐波那契。计算根本不适合并行化。

于 2011-07-02T05:29:15.850 回答
1

这种递归将很快溢出堆栈。这是因为您一遍又一遍地计算较低的斐波那契数 - 指数倍数。

避免这种情况的一种有效方法是使用记忆递归（一种动态编程方法）

基本上使用静态数组来保存已经计算出的斐波那契数，当你需要一个时，如果它已经被计算过，就从数组中取出它。如果不是，则计算它并将其存储在数组中。这样每个数字将只计算一次。

（当然可以用其他数据结构代替数组，即hashtable）

于 2011-07-02T04:56:48.387 回答
0

当您有独立的任务要执行时，线程工作得最好。根据定义，斐波那契数列没有任何程度的并行性。每个 f(n) 取决于前两个值。因此，使用多个线程计算 f(n) 的速度不可能比使用一个线程快（除非您的算法效率低下）

唯一可以并行+处理大量数据的操作，但是这可能是 a) 复杂 b) 难以比单线程解决方案更快。

计算斐波那契数的最快/最简单的方法是在一个线程中使用循环。您不需要使用 recursion 或记忆值。

于 2011-07-02T14:05:45.300 回答