我有两种测试中的斐波那契方法。两个方法都应该是线性的。要么我不理解记忆化,要么HashMap查找比我想象的慢。
我知道递归函数不会因为DP而加速很多,但由于它是静态的,所以只需要计算一次(永远不会超出范围)。在第一次执行后,它将从HashMap中检索答案。
我正在为实现O(log n)斐波那契函数做准备和基准测试,但当我看到这个问题时,稍微走了点弯路。(甚至将记忆化添加到迭代方法也会使其变慢)。
请给我指点,我感觉自己很愚蠢。
迭代方法:
我知道递归函数不会因为DP而加速很多,但由于它是静态的,所以只需要计算一次(永远不会超出范围)。在第一次执行后,它将从HashMap中检索答案。
我正在为实现O(log n)斐波那契函数做准备和基准测试,但当我看到这个问题时,稍微走了点弯路。(甚至将记忆化添加到迭代方法也会使其变慢)。
请给我指点,我感觉自己很愚蠢。
迭代方法:
public static int linearIterativeFib(int x) {
if (x <= 2) {
return 1;
} else {
int prev = 0;
int result = 1;
for (int i = 2; i <= x; i++) {
int temp = result;
result += prev;
prev = temp;
}
return result;
}
}
递归算法:
static Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
public static int linearRecursiveFib(int x) {
if (x <= 2) {
return 1;
} else if (memo.containsKey(x)) {
return memo.get(x);
} else {
int result = linearRecursiveFib(x - 1)
+ linearRecursiveFib(x - 2);
memo.put(x, result);
return result;
}
}
还有一个单元测试:
@Test
public void testSpeed() {
int input = 35;
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
fib.linearIterativeFib(input);
}
System.out.println("Iterative approach took "
+ (System.currentTimeMillis() - start) + "ms");
start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
fib.linearRecursiveFib(input);
}
System.out.println("Recursive approach took "
+ (System.currentTimeMillis() - start) + "ms");
}
返回值:
Iterative approach took 6ms
Recursive approach took 132ms
int[]
代替HashMap
,结果仅相差2倍。递归仍然较慢。 - Jorn Vernee