动态编程实现不佳还是 HashMap 慢？

Question

我正在测试两种斐波那契方法。两者都应该是线性的。要么我不理解记忆，要么 HashMap 查找比我想象的要慢。

我知道递归函数不应该通过添加 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

Answer 1

首先，java中的递归比迭代慢。

与其先执行 contains 然后再获取，为什么不直接获取并执行 null 检查呢？hash和bucket需要计算两次，不知道对性能影响有多大。

自动装箱。使用带有原始映射的外部库可能是个好主意，例如 gnu Trove。不确定性能增益会是多少，但您将分配更少的对象。

检查性能测量是否合理也是一个好主意。在递归情况下，第一次或前几次迭代是否比其余迭代慢？平均值可能不是一个好的测量值。如果有延迟直方图就好了。