在java中使用线程计算斐波那契

Question

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

我想用java线程计算斐波那契序列，以减少计算时间，但答案是错误的，尽管它似乎是正确的。 另一个问题是在启动第 35 号到顶部的新线程时发生内存不足异常。 请帮我 许多问候...

Answer 1

你说你这样做是为了提高性能。有几个问题：

• 您永远不会通过在此使用线程来减少计算时间
  方式。
• 如果您关心性能，那么递归不是一个好主意
  这个问题。

只需一个线程、一个简单的循环和两个变量，您将获得性能方面难以超越的东西（不使用 一个封闭形式的解决方案，即）。

Answer 2

请参阅斐波那契数 (Java)，记忆递归。这应该会让您了解如何实施快速解决方案。

Answer 3

您需要限制线程数量。我建议您只使用两个线程：一个用于查找索引 - 1，另一个用于查找索引 - 2。当这些方法中的每一个递归地查找前一个索引 - 1 和索引 - 2 时，请在现有线程中执行此操作。

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

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

最后，我相信前两个斐波那契数（根数）是 1 和 1。 2、不是0& 1. 请注意，我将 getNumber 更改为返回 index + 1 并递归调用自身，而不是返回到服务。

1 + 2 = 3 + 2 = 5 ...

0 + 1 = 1（错误）

该算法的另一个问题是它做了两次大量工作，因为它重新计算值。例如，如果您正在查找

F5 = F4 + F3

线程 1：F4 = F3 + F2

线程 2：F3 = F2 + F1

请注意，您计算了 F3 两次。事实上，您几乎每个数字都计算了两次。