I've got two Fibonacci methods I'm testing out. Both should be linear. Either I don't understand memoization or HashMap lookups are slower than I thought.
I understand that the recursive function shouldn't be sped up a lot by the addition of DP, but since it's static it only needs to compute once (never falls out of scope). After the first execution, it retrieves the answer from the HashMap.
I'm doing this in preparation for implementing the O(log n) fibonacci function and benchmarking, but got detoured slightly when I saw this. (Even addition memoization to the iterative approach slows it down).
Please enlighten me, I'm feeling quite stupid at the moment.
Iterative Approach:
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;
}
}
Recursive Approach:
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;
}
}
And a unit test:
@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");
}
Returns:
Iterative approach took 6ms
Recursive approach took 132ms
