3

我只是在Java中测试河内塔问题，我运行了以下代码：（为方便起见，我已删除）sysouts

public class Util {

    public static void main(String[] args) {
        for (int i = 1; i <= 30; i++) {
            long startTime = System.currentTimeMillis();
            solveTowerOfHanoi(i, "A", "B", "C");
            System.out.println("Time taken for " + i + ": "
                    + (System.currentTimeMillis() - startTime));
        }
    }

    public static void solveTowerOfHanoi(int n, String src, String inter,
            String dest) {
        if (n == 0) {
            return;
        }
        solveTowerOfHanoi(n - 1, src, dest, inter);
        solveTowerOfHanoi(n - 1, inter, src, dest);
    }
}

我做了一个实验，我尝试了从 1 到 35 的磁盘大小（索引），我观察到一个非常奇怪的时序模式，这是程序的输出：

Time taken for 1: 0
Time taken for 2: 0
Time taken for 3: 0
Time taken for 4: 0
Time taken for 5: 0
Time taken for 6: 0
Time taken for 7: 0
Time taken for 8: 1
Time taken for 9: 0
Time taken for 10: 0
Time taken for 11: 0
Time taken for 12: 0
Time taken for 13: 0
Time taken for 14: 0
Time taken for 15: 0
Time taken for 16: 0
Time taken for 17: 0
Time taken for 18: 3
Time taken for 19: 2
Time taken for 20: 11
Time taken for 21: 10
Time taken for 22: 39
Time taken for 23: 37
Time taken for 24: 158
Time taken for 25: 147
Time taken for 26: 603
Time taken for 27: 579
Time taken for 28: 2414
Time taken for 29: 2304
Time taken for 30: 9509
Time taken for 31: 9408
Time taken for 32: 38566
Time taken for 33: 37531
Time taken for 34: 152255
Time taken for 35: 148704

问题 1：算法有指数增长(2^n-1)，那么为什么我看不到从 1-20 的时间逐渐增长？但是然后突然从20-35跳跃？

问题2：还有一件更让我吃惊的事情是成对的时间相等。从 19 日开始，(19,20)、(21,22)、(23,24)、(25,26) 等......有可比的时间。我无法理解这一点，如果算法的增长率确实是指数级的，为什么两个索引给出几乎可比的时间，然后在下一个索引处突然跳跃？

注意：我重复了这个程序 2-3 次，得到了几乎可比的时间，所以你可以把它当作一个平均运行。

编辑
尝试System.nanoTime()并得到以下结果：

Time taken for 1: 62644
Time taken for 2: 3500
Time taken for 3: 3500
Time taken for 4: 4200
Time taken for 5: 6300
Time taken for 6: 7350
Time taken for 7: 11549
Time taken for 8: 19948
Time taken for 9: 47245
Time taken for 10: 73142
Time taken for 11: 87491
Time taken for 12: 40246
Time taken for 13: 39196
Time taken for 14: 156784
Time taken for 15: 249875
Time taken for 16: 593541
Time taken for 17: 577092
Time taken for 18: 2318166
Time taken for 19: 2305217
Time taken for 20: 9468995
Time taken for 21: 9082284
Time taken for 22: 37747543
Time taken for 23: 37230646
Time taken for 24: 150416580
Time taken for 25: 145795297
Time taken for 26: 603730414
Time taken for 27: 578825875
Time taken for 28: 2409932558
Time taken for 29: 2399318129
Time taken for 30: 9777009489

输出几乎与毫秒相似，但它确实使画面清晰......回答我的问题 1可能是，但问题 2仍然很有趣。并System.nanoTime()提出了另一个问题：

问题 3：为什么索引 1 比下一个索引 (2,3...) 等花费更多时间？

4

2 回答 2

2

答案 1：在您开始玩 18 张光盘之前，您的计时测量太粗略，无法显示任何有用的信息。不建议您就运行时间的变化与此值范围内的磁盘数量得出任何结论。

答案 2：由于已经对河内塔问题进行了大量研究，并且它的时间复杂度众所周知，因此您不太可能遇到具有更好时间复杂度的实现。因此，我们可能会得出结论，您的实现有一些特殊的东西会导致程序连续运行中的执行时间大致相等。

我不能立即看出你的 Java 有什么问题，所以我会直接得出结论，你的系统返回的时间有些奇怪。

编辑

纳米计时显示出与毫计时相似的结构。不过，我注意到，虽然 27 个磁盘和 28 个磁盘的毫秒计时相似，然后大幅跃升至 29 个磁盘，但纳米计时从 27 个磁盘大幅跃升至 28 个，然后类似于时间为 29 个磁盘。

至于新问题 3：我建议 OP 通过运行主循环两次来“启动”JIT 和 JVM，丢弃第一次运行的结果。我想我也会在调用之外获得结束时间System.out.println，例如：

long startTime = System.currentTimeMillis();
solveTowerOfHanoi(i, "A", "B", "C");
long endTime = System.currentTimeMillis();
System.out.println("Time taken for " + i + ": " + (endTime - startTime));

编辑 2

回应OP的评论......

对于 1 个磁盘比 2 个磁盘需要更长的时间来解决问题的一般解释之一是，您的时间包括幕后的“启动内容”——如果我正确地记得我的 Java 教育（我可能不记得）Java 编译器会创建字节码和运行时系统将字节码翻译成机器码。您可能（Java 专家在这里随意吐槽）正在安排第二次翻译的时间。至于 JIT，一般的方法是即时编译器只有在其对代码的动态分析表明它应该启动时才会启动。它可能只在第二轮优化您的代码。

编辑 3

好的，我接受了诱饵并定时了 2 个版本的代码，第一个（下面的第 2 列）与原始问题中的完全一样，第二个（下面的第 3 列）使用nanoTime而不是currentTimeMillis. 我的结论是

  1. 正如我最初断言的那样，OP 的系统有些可疑。我在第 2 列中显示的时间非常符合预期，因此这不是一般的 Java 问题。
  2. 我的机器上的实现存在严重错误nanoTime，或者我对它的理解存在严重问题。这增加了我最初断言背后的思考，很容易被计算机时钟误导，它们提供的结果不能总是以表面价值看待。

在开始计时之前，我还测试了启动 JIT/JVM，最后它几乎没有影响，所以我没有在这里包含这些数据。

| Discs | milliS | nanoS      |
|    1: |      0 |       7000 |
|    2: |      0 |       4000 |
|    3: |      0 |       6000 |
|    4: |      0 |      11000 |
|    5: |      0 |      22000 |
|    6: |      0 |      43000 |
|    7: |      0 |      84000 |
|    8: |      0 |     172000 |
|    9: |      1 |     331000 |
|   10: |      0 |     663000 |
|   11: |      2 |    1334000 |
|   12: |      2 |    2632000 |
|   13: |      6 |    5265000 |
|   14: |     11 |   10476000 |
|   15: |     21 |   22034000 |
|   16: |     42 |   43407000 |
|   17: |     85 |   89683000 |
|   18: |    169 |  171209000 |
|   19: |    337 | -655065000 |
|   20: |    673 |  688203000 |
|   21: |   1345 | -814465000 |
|   22: |   2708 |  707742000 |
|   23: |   5531 | -533716000 |
|   24: |  10918 | -140615000 |
|   25: |  21542 |  628928000 |
|   26: |  42889 |   97892000 |
|   27: |  85698 |  325197000 |
|   28: | 172370 |  -80280000 |
|   29: | 345650 |  110795000 |
|   30: | 685006 |  453388000 |

笔记：

javac -v => Eclipse Java Compiler v_677_R32x, 3.2.1 release, Copyright IBM Corp 2000, 2006. All rights reserved.

java --version => java version "1.4.2"
gij (GNU libgcj) version 4.1.2 20071124 (Red Hat 4.1.2-42)
于 2012-06-26T09:53:30.360 回答
0

当我们谈论程序的复杂性分析时，它意味着渐近地研究复杂性。就您的计时数据而言，您从中得出了指数增长和其他有趣的特征（如平等），我可以简单地说，当您拥有一些数据并盯着它一段时间时，您会得到有趣的模式:)

因此，从您的时序数据中得出的关于问题理论复杂性的任何结论Tower Of Hanoi都是垃圾。

但是，如果您对为什么代码实际上显示出如此观察到的指数增长感兴趣，它可能归因于 java 使用的 RAM 量。

于 2012-06-26T09:52:03.433 回答