Java – poor implementation of dynamic programming or slow HashMap?

See English answers > How do I write a correct micro benchmark in Java? 11

I know that recursive functions should not be accelerated by adding DP, but because it is static, it only needs to be calculated once (never out of range) After the first execution, it retrieves the answer from the HashMap

I did this to prepare for the implementation of O (log n) Fibonacci functions and benchmarks, but when I saw this, I would make a slight detour Even adding memoization to an iterative method slows it down

Please enlighten me. I feel silly at the moment

Iterative method:

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 method:

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

return:

Iterative approach took 6ms
Recursive approach took 132ms

Solution

First, recursion in Java is slower than iteration

Instead of including and getting, why not just get and do an empty check? Hash and bucket need to be calculated twice, and it is uncertain how much the performance impact is

Automatic packing It may be a good idea to use an external library with the original map, such as GNU trove I'm not sure what the performance gain will be, but you'll allocate fewer objects

It is also a good idea to check whether the performance measurement is reasonable In the case of recursion, is the first or previous iteration slower than the rest? The average may not be a good measure It would be nice to have a delay histogram