0

我正在尝试为杆切割问题实施简单的解决方案。下面是天真和动态编程解决方案的代码，

public static int rodCutNaive(int[] a, int n) {
    if (n == 1) {
        return a[0];
    }
    int q = 0;
    for (int i = 1; i <= n; i++) {
        int optimalCut = a[i - 1] + rodCutNaive(a, n - i);
        if (q < optimalCut) {
            q = optimalCut;
        }
    }
    return q;
}

public static int rodCutDPBottomUp(int[] a, int n) {
    if (n == 1) {
        return a[0];
    }
    int[] s = new int[a.length];
    s[0] = a[0];

    for (int i = 2; i <= n; i++) {
        s[i - 1] = a[i - 1];
        for (int j = 1; j <= i - 1; j++) {
            int optimalCut = a[j - 1] + s[i - j - 1];
            if (s[i - 1] < optimalCut) {
                s[i - 1] = optimalCut;
            }
        }
    }

    return s[n - 1];
}

我用下面的方法测试了，

public void testRodCutEfficiency() {
    int[] a = { 1, 5, 8, 9, 10, 17, 17, 20, 22, 25, 26, 29, 34, 35, 39, 45,
            46, 47, 50, 51 };

    long t1 = System.nanoTime();
    for (int i = 0; i < 1000; i++)
        Rod.rodCutNaive(a, a.length);
    long t2 = System.nanoTime();
    for (int i = 0; i < 1000; i++)
        Rod.rodCutDPBottomUp(a, a.length);
    long t3 = System.nanoTime();

    System.out.println("Problem size = " + a.length);
    System.out.println("Naive = " + (t2 - t1));
    System.out.println("DP    = " + (t3 - t2));
}

输出：

Problem size = 20
Naive = 7989627046
DP    = 7913165707

可能是编译器对天真的版本进行了某种尾递归优化，还是 JVM 可能会记住以前调用方法的解决方案？

哦，对不起，伙计们。这是复制粘贴错误。我两次都调用了相同的方法。现在我改变了它，新的输出是，

Problem size = 20
Naive = 7764056945
DP    = 1324966

我试图删除这个问题，但它已经有了答案。

4

3 回答 3

2

可能是编译器对天真的版本进行了某种尾递归优化，还是 JVM 可能会记住以前调用方法的解决方案？

编译器javac几乎不做任何优化，但是 JIT 会在迭代 10,000 次后优化代码，这会影响您的结果。

HotSpot JVM 不支持尾递归优化，它不记得以前的结果。

如果我反复运行测试，我会看到小的改进

Problem size = 20
Naive = 5792466746
DP    = 8779592

到

Problem size = 20
Naive = 5701799026
DP    = 472377
于 2012-11-15T11:05:18.300 回答
1

您两次都调用 rodCutNaive。

于 2012-11-15T11:20:51.733 回答
1

所以，是的，基本上，如果你改变第二个基准循环来对动态方法进行基准测试，你会得到这个显着的加速：

问题大小 = 20

天真 = 3838585219

DP = 798526

于 2012-11-15T11:25:21.517 回答