使斐波那契更快 [英] Making Fibonacci faster
问题描述
我被要求写一个简单的Fibonacci算法实现，然后让它更快。
I was required to write a simple implementation of Fibonacci's algorithm and then to make it faster.
这是我的初始实现
public class Fibonacci {
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return getFibonacciOf(n-2) + getFibonacciOf(n-1);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}
}
正如您所看到的，我正在使用System.currentTimeMillis（）来计算计算Fibonacci时所经过的时间。
As you can see I am using System.currentTimeMillis() to get a simple measure of the time elapsed while computed Fibonacci.
这种实现方式快速呈指数级增长，如下图所示
所以我有一个简单的优化想法。要将先前的值放在HashMap中，而不是每次都重新计算它们，只需将它们从HashMap中取回（如果它们存在）。如果它们不存在，我们将它们放在HashMap中。
这是代码的新版本
public class FasterFibonacci {
private static Map<Long, Long> previousValuesHolder;
static {
previousValuesHolder = new HashMap<Long, Long>();
previousValuesHolder.put(Long.valueOf(0), Long.valueOf(0));
previousValuesHolder.put(Long.valueOf(1), Long.valueOf(1));
}
public static long getFibonacciOf(long n) {
if (n== 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if (previousValuesHolder.containsKey(Long.valueOf(n))) {
return previousValuesHolder.get(n);
} {
long newValue = getFibonacciOf(n-2) + getFibonacciOf(n-1);
previousValuesHolder.put(Long.valueOf(n), Long.valueOf(newValue));
return newValue;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
while (true) {
System.out.println("Enter n :");
long n = scanner.nextLong();
if (n >= 0) {
long beginTime = System.currentTimeMillis();
long fibo = getFibonacciOf(n);
long endTime = System.currentTimeMillis();
long delta = endTime - beginTime;
System.out.println("F(" + n + ") = " + fibo + " ... computed in " + delta + " milliseconds");
} else {
break;
}
}
}
这一变化使计算速度极快。我立刻计算了从2到103的所有值，并且在F（104）处得到长溢出（给我F（104）= -7076989329685730859，这是错误的< /强>）。我发现它太快了**我想知道我的代码是否有任何错误（谢谢你的检查，请告诉我）**。请看第二张图片：
This change makes the computing extremely fast. I computes all the values from 2 to 103 in no time at all and I get a long overflow at F(104) (Gives me F(104) = -7076989329685730859, which is wrong). I find it so fast that **I wonder if there is any mistakes in my code (Thank your checking and let me know please) **. Please take a look at the second picture:
我的更快的斐波纳契算法的实现是否正确（看来这对我来说是因为它与第一个版本的值相同，但是因为第一个版本太慢了我无法用它来计算更大的值，如F（75））？还有什么方法可以让它更快？还是有更好的方法让它更快？同样如何计算斐波纳契以获得更大的值（例如150,200）而不会出现**长溢出**？虽然看起来很快，但我想把它推到极限。我记得Abrash先生说'最好的优化者在你的双耳之间'，所以我相信它仍然可以改进。感谢您的帮助
Is my faster fibonacci's algorithm's implementation correct (It seems it is to me because it gets the same values as the first version, but since the first version was too slow I could not compute bigger values with it such as F(75))? What other way can I use to make it faster? Or is there a better way to make it faster? Also how can I compute Fibonacci for greater values (such as 150, 200) without getting a **long overflow**? Though it seems fast I would like to push it to the limits. I remember Mr Abrash saying 'The best optimiser is between your two ears', so I believe it can still be improved. Thank you for helping
[版本注意：] 虽然这个问题解决了我的问题中的一个主要观点，你可以从上面看到我有其他问题。
Though this question adresses one of the main point in my question, you can see from above that I have additionnal issues.
推荐答案
动态编程
Dynamic programming
创意：不是多次重新计算相同的值，而是只存储计算的值并在使用时使用它们。
Idea:Instead of recomputing the same value multiple times you just store the value calculated and use them as you go along.
f（n）= f（n-1）+ f（n-2） f（0）= 0，f（1）= 1。
因此，当您计算f（n-1）时，如果存储f（n）和f（n-1）的值，则可以轻松计算f（n）。
f(n)=f(n-1)+f(n-2) with f(0)=0,f(1)=1.
So at the point when you have calculated f(n-1) you can easily calculate f(n) if you store the values of f(n) and f(n-1).
让我们先来看一系列Bignums。 A [1..200]。
将它们初始化为-1。
Let's take an array of Bignums first. A[1..200]. Initialize them to -1.
fact(n)
{
if(A[n]!=-1) return A[n];
A[0]=0;
A[1]=1;
for i=2 to n
A[i]= addition of A[i],A[i-1];
return A[n]
}
这在 O中运行（n）时间。自己检查一下。
This runs in O(n) time. Check it out yourself.
此技术也称为 memoization 。
动态编程（通常称为DP）是解决特定类问题的一种非常强大的技术。它要求非常优雅的方法和简单的思维，编码部分非常容易。这个想法非常简单，如果你已经解决了给定输入的问题，那么保存结果以供将来参考，以避免再次解决同样的问题。不久'记住你的过去'。
Dynamic programming (usually referred to as DP ) is a very powerful technique to solve a particular class of problems. It demands very elegant formulation of the approach and simple thinking and the coding part is very easy. The idea is very simple, If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.. shortly 'Remember your Past'.
如果给定的问题可以分解为较小的子问题，而这些较小的子问题又被分成更小的子问题，并且在这个过程中，如果你观察到一些过度使用的子问题，那么这是DP的一个重要提示。此外，子问题的最优解决方案有助于解决给定问题的最优解（称为最优子结构属性）。
If the given problem can be broken up in to smaller sub-problems and these smaller subproblems are in turn divided in to still-smaller ones, and in this process, if you observe some over-lappping subproblems, then its a big hint for DP. Also, the optimal solutions to the subproblems contribute to the optimal solution of the given problem ( referred to as the Optimal Substructure Property ).
有两种方法可以做到这一点。
There are two ways of doing this.
1。）自上而下：通过破解解决给定问题下。如果您发现问题已经解决，那么只需返回已保存的答案。如果尚未解决，请解决并保存答案。这通常很容易想到并且非常直观。这称为Memoization。 （我已经使用了这个想法）。
1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization. (I have used this idea).
2。）自下而上：分析问题并查看子问题的解决顺序并从中解决问题微不足道的子问题，直到给定的问题。在此过程中，保证在解决问题之前解决子问题。这称为动态编程。 （ MinecraftShamrock 使用了这个想法）
2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming. (MinecraftShamrock used this idea)
还有更多！
（其他方法）
There's more!
(Other ways to do this)
看看我们追求更好解决方案并未在此结束。您将看到不同的方法 -
Look our quest to get a better solution doesn't end here. You will see a different approach-
如果您知道如何解决
重现关系然后你会找到这种关系的解决方案
If you know how to solve
recurrence relationthen you will find a solution to this relation
f（n）= f（n-1）+ f（n-2）给定f（0）= 0，f（1）= 1
解决后你将得到公式它 -
You will arrive at the formula after solving it-
f（n）=（1 / sqrt（5））（（1 + sqrt（5））/ 2）^ n - （1 / sqrt（5））（（1-sqrt（5））/ 2）^ n
可写成更紧凑的形式
f（n）= floor（（（（1 + sqrt（5））/ 2）^ n）/ sqrt（ 5）+ 1/2）
你可以获得权力 O（logn）操作中的数字。
你必须学习通过平方的指数化。
You can get the power a number in O(logn) operations. You have to learn the Exponentiation by squaring.
编辑：值得指出的是，这并不一定意味着可以在O（logn）中找到斐波纳契数。实际上我们需要计算的位数线性地计算。可能是因为我说它似乎声称错误的想法可以在O（logn）时间内计算数字的阶乘。
[Bakurui，MinecraftShamrock对此发表评论]
EDIT: It is good to point out that this doesn't necessarily mean that the fibonacci number can be found in O(logn). Actually the number of digits we need to calculate frows linearly. Probably because of the position where I stated that it seems to claim the wrong idea that factorial of a number can be calculated in O(logn) time. [Bakurui,MinecraftShamrock commented on this]
这篇关于使斐波那契更快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
