动态规划实现不佳还是HashMap慢？

Question

动态规划实现不佳还是HashMap慢？

javarecursionhashmapdynamic-programmingfibonacci

5

我有两种测试中的斐波那契方法。两个方法都应该是线性的。要么我不理解记忆化，要么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

- Jonas Schreiber

我猜这是因为递归涉及到推入和弹出堆栈内容。 - Jo Kachikaran

很可能存在显著的性能差异，但基准测试JIT运行时需要谨慎措施。如果您仍然有显著的性能差异需要检查，请重新构建您的基准测试并编辑或发布一个新问题。 - chrylis -cautiouslyoptimistic-

我尝试了使用int[]代替HashMap，结果仅相差2倍。递归仍然较慢。 - Jorn Vernee

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sason Ohanian · Answer 1

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

与其进行contains然后get操作，为什么不直接get并进行null检查呢？哈希和桶需要计算两次，不确定性能影响有多大。

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

还可以检查性能测量是否准确。在递归情况下，前几次迭代是否比其余迭代慢得多？平均值可能不是一个好的测量标准。最好有一个延迟直方图。