用java中的线程计算斐波那契线程

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

im gonig用java线程计算斐波那契数列以减少计算时间但答案错误虽然它似乎是真的。另一个问题是在编号为35的新线程顶端出现内存不足异常。请帮帮我很多问候...用java中的线程计算斐波那契线程

来源

2011-10-06 Riporter

是什么让你觉得使用线程在这里会有所帮助？有一种天然的O（n）解决方案是不可并行的......这是一种比所有这些复杂性更好的方法，IMO。 –

你是否意识到每次递归都会使得任务数量增加一倍？为你自己判断你的计算机系统将承担多长时间，假设一个任务需要* some *内存（例如，我们可以假设一个任务只需要4个字节，需要多少次递归来填充你的内存？） – Ingo

您需要限制线程数。我建议你只使用两个线程：一个用于查找索引-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 & 2，不是0 & 1.请注意，我改变了getNumber返回index + 1和递归调用本身，而不是要回服务。

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

0 + 1 = 1（误差）

另一个问题本ALG具有是做了很多工作的两倍，因为它重新计算的值。例如，如果您正在寻找

F5 = F4 + F3

线程1：F4 = F3 + F2

线程2：F3 = F2 + F1

请注意，您计算F3两次。事实上，你正在计算每个数字两次。

来源

2011-10-06 11:07:39

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

您永远不会通过使用此方法中的线程来减少计算时间。
如果你关心性能，递归对于这个问题是一个坏主意。

只要有一个线程，一个简单的循环和两个变量，你就会有一些将是很难被击败的性能代价（不使用a closed-form solution，这是）。

来源

2011-10-06 11:07:46 NPE

请参阅Fibonacci numbers (Java)，memoized递归。这应该给你一个关于如何实现快速解决方案的想法。

来源

2011-10-06 11:11:56 helpermethod

用java中的线程计算斐波那契线程

回答

相关问题