算法(4th ed)(149):基础——算法分析 6.2.2

阅读数:23 2019 年 11 月 6 日 07:52

算法(4th ed)(149):基础——算法分析 6.2.2

(观察:计时器)

准确测量给定程序的确切运行时间是很困难的。不过幸运的是我们一般只需要近似值就可以了。我们希望能够把需要几秒钟或者几分钟就能完成的程序和需要几天、几个月甚至更长时间才能完成的程序区别开来,而且我们希望知道对于同一个任务某个程序是不是比另一个程序快一倍。因此,我们仍然需要准确的测量手段来生成实验数据,并根据它们得出并验证关于程序的运行时间和问题规模的假设。为此,我们使用了如表 1.4.1 所示的Stopwatch 数据类型。它的 elapsedTime() 方法能够返回自它创建以来所经过的时间,以秒为单位。它的实现基于 Java 系统的 currentTimeMillis() 方法,该方法能够返回以毫秒记数的当前时间。它在构造函数中保存了当前时间,并在 elapsedTime() 方法被调用时再次调用该方法来计算得到对象创建以来经过的时间。

表 1.4.1 一种表示计时器的抽象数据类型

APIpublic class Stopwatch
             Stopwatch()创建一个计时器
    double   elapseTime()返回对象创建以来所经过的时间
典型用例
public static void main(String[] args)
{
int N = Integer.parseInt(args[0]);
int[] a = new int[N];
for (int i = 0; i ^lt; N; i++)
a[i] = StdRandom.uniform(-1000000, 1000000);
Stopwatch timer = new Stopwatch();
int cnt = ThreeSum.count(a);
double time = timer.elapsedTime();
StdOut.println(cnt + " triples " + time + " seconds");
}

使用方法
% java Stopwatch 1000
51 triples 0.488 seconds
% java Stopwatch 2000
516 triples 3.855 seconds

数据类型的实现
public class Stopwatch
{
private final long start;
public Stopwatch()
{ start = System.currentTimeMillis(); }
public double elapsedTime()
{
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}

评论

发布