1

我正在比较在 Java 中计算迭代和递归阶乘过程的时间。我正在尝试使用该System.currentTimeMillis方法来比较每种算法计算所需的时间，但我似乎无法计算出差异。我不确定使用此方法的正确方法是什么，但这里的任何事件都是我试图在我的代码中实现的：

// ... more code above

System.out.print("Please enter an integer: ");
int integer = readInt();
System.out.println();

// demonstrate recursive factorial and calculate
// how long it took to complete the algorithm
long time1 = System.currentTimeMillis();
int fact1 = factRecursive(integer);
long time2 = System.currentTimeMillis();
System.out.format("Result of recursive factorial %s is %d\n", integer, fact1);
System.out.format("Algorithm took %d milliseconds\n\n", (time2 - time1));

// ... more code below

这是输出：

Please enter an integer: 25

Result of recursive factorial 25 is 2076180480
Algorithm took 0 milliseconds

Result of iterative factorial 25 is 2076180480
Algorithm took 0 milliseconds

显然我在这里做错了，因为计算这两种情况的阶乘的预期时间不应该为零。

编辑：如果有人感兴趣，这是我的阶乘解决方案（不是特别独特，但无论如何它们都在这里）：

// factRecursive uses a recursive algorithm for 
// caluclating factorials.
public static long factRecursive(long n)
{
    return n = (n == 1)? 1 : n * factRecursive(n - 1);
}

// factIterative uses an iterative algorithm for
// calculating factorials.
public static long factIterative(long n)
{
    long product = 1;

    if(n == 1) return n;

    for(int i = 1; i <= n; ++i)
        product *= i;

    return product;
}

并且是一些输出。令人惊讶的是，递归版本的效果很好。还没到39点左右！迭代版本开始表现得明显更好。

Please enter an integer: 39

Result of recursive factorial 39 is 2304077777655037952
Algorithm took 5828 nanoseconds

Result of iterative factorial 39 is 2304077777655037952
Algorithm took 5504 nanoseconds
4

6 回答 6

4

的分辨率System.currentTimeMillis()可能会有所不同，具体取决于您的系统；看来您的算法太快了，无法使用此计时器进行测量。

改为使用System.nanoTime()。它的准确性也取决于系统，但至少它能够进行高分辨率时间测量。

即时编译会对性能产生很大影响，但大多数虚拟机需要在重新编译之前多次调用某个方法。这使得很难从这种微基准中获得准确的结果。

于 2012-04-11T01:19:53.227 回答
3

一个编写良好的阶乘函数在 n = 25 时执行得非常快，所以让它在大约 0 毫秒内运行并不令人惊讶。你有三个选择：

  1. 使用更大的 n。这将导致阶乘函数花费更长的时间，并为您提供一些要测量的东西。
  2. 使用System.nanoTime以近似纳秒而不是毫秒来测量时间。
  3. 我建议同时执行 1 和 2。

正如其他回答者指出的那样，您确实是从 start 中减去 end ，这是倒退的。显然，你也应该解决这个问题。但这种变化只影响结果的符号，而不影响绝对值。

编辑：只是为了看看找到 25 的阶乘有多快，我写了这个 Python 实现

>>> def fact(n):
...     def _fact(n, acc):
...             if n == 1:
...                     return acc
...             return _fact(n - 1, n * acc)
...     if n < 0:
...             return 0 # Or raise an exception
...     if n < 2:
...             return 1
...     return _fact(n, 1)
... 
>>> fact(25)
15511210043330985984000000L
>>> import timeit
>>> t = timeit.Timer("fact(25)", "from __main__ import fact")
>>> print t.timeit()
6.2074379921

尽管 Python 是一种没有尾调用优化的解释型动态类型语言，但带有累加器的简单递归解决方案可以fact(25)在我的机器上在 6.2 秒内找到一百万次。所以平均执行时间是 6.2 微秒。没有机会以毫秒时钟精度在一次运行中测量迭代和递归解决方案之间的实质性差异。

于 2012-04-11T01:18:30.073 回答
1

你需要做（完成时间 - 开始时间），你有它倒退。

试试这个：

System.out.format("Algorithm took %d milliseconds\n\n", (time2 - time1));
于 2012-04-11T01:16:43.557 回答
1

很常见的错误。您应该从 time2 中减去 time1。

如果您明智地命名变量，这将有所帮助 - 例如startTime，endTime您会知道或至少发现您必须这样endTime - startTime做endTime>startTime

于 2012-04-11T01:18:25.940 回答
1

看起来您的快速递归毕竟可能没有进行如此繁重的处理。

请System.nanoTime()改用。它返回纳秒

http://docs.oracle.com/javase/7/docs/api/java/lang/System.html

nanoTime() 返回正在运行的 Java 虚拟机的高分辨率时间源的当前值，以纳秒为单位。

另一种测试方法是迭代你的阶乘，比如 1000 次。然后将时间差除以 1000.00（双倍）

于 2012-04-11T01:20:12.460 回答
0

要获得有意义的定时结果，您需要重复并忽略至少前 10,000 次调用方法（因此代码已编译），并且您需要再运行 2-10 秒（重复）。

于 2012-04-11T06:02:50.427 回答