Course navigation & on this page
Stopwatch utility
Measure elapsed wall-clock time around an algorithm experiment.
Overview
Measure elapsed wall-clock time around an algorithm experiment. The utility stores a starting time and subtracts it from the current time. The algorithm being measured has its own cost. Millisecond wall-clock timing has finite resolution and can reflect unrelated system activity.
Step-by-step walkthrough
- Construct a Stopwatch immediately before the measured region.
- Run the selected operation.
- Call elapsedTime to obtain seconds since construction.
- Record the input and environment with the result.
Complexity analysis
| Best case | Θ(1) per timing call |
|---|---|
| Average / aggregate | Θ(1) per timing call |
| Worst case | Θ(1) per timing call in the unit-cost model |
| Space | Θ(1) |
The utility stores a starting time and subtracts it from the current time. The algorithm being measured has its own cost. Millisecond wall-clock timing has finite resolution and can reflect unrelated system activity.
A worked example
Create the timer, call ThreeSum.count(a), then read elapsedTime without including file loading if the goal is to time only the counter.
Common mistake / implementation note
The example main in the utility demonstrates timing; its loop cost is not the cost of the stopwatch itself.
The example main in the utility demonstrates timing; its loop cost is not the cost of the stopwatch itself.
Original course code
Source: code/Stopwatch.java. Original logic, comments, variable names and attribution are retained.
Download Stopwatch.javaStopwatch.javaJAVA
/****************************************************************************** * Compilation: javac Stopwatch.java * Execution: java Stopwatch n * Dependencies: none * * A utility class to measure the running time (wall clock) of a program. * * % java8 Stopwatch 100000000 * 6.666667e+11 0.5820 seconds * 6.666667e+11 8.4530 seconds * ******************************************************************************/ // package edu.princeton.cs.algs4; /** * The {@code Stopwatch} data type is for measuring * the time that elapses between the start and end of a * programming task (wall-clock time). * * See {@link StopwatchCPU} for a version that measures CPU time. * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/14analysis">Section 1.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Stopwatch { private final long start; /** * Initializes a new stopwatch. */ public Stopwatch() { start = System.currentTimeMillis(); } /** * Returns the elapsed CPU time (in seconds) since the stopwatch was created. * * @return elapsed CPU time (in seconds) since the stopwatch was created */ public double elapsedTime() { long now = System.currentTimeMillis(); return (now - start) / 1000.0; } /** * Unit tests the {@code Stopwatch} data type. * Takes a command-line argument {@code n} and computes the * sum of the square roots of the first {@code n} positive integers, * first using {@code Math.sqrt()}, then using {@code Math.pow()}. * It prints to standard output the sum and the amount of time to * compute the sum. Note that the discrete sum can be approximated by * an integral - the sum should be approximately 2/3 * (n^(3/2) - 1). * * @param args the command-line arguments */ public static void main(String[] args) { int n = Integer.parseInt(args[0]); // sum of square roots of integers from 1 to n using Math.sqrt(x). Stopwatch timer1 = new Stopwatch(); double sum1 = 0.0; for (int i = 1; i <= n; i++) { sum1 += Math.sqrt(i); } double time1 = timer1.elapsedTime(); StdOut.printf("%e (%.2f seconds)\n", sum1, time1); // sum of square roots of integers from 1 to n using Math.pow(x, 0.5). Stopwatch timer2 = new Stopwatch(); double sum2 = 0.0; for (int i = 1; i <= n; i++) { sum2 += Math.pow(i, 0.5); } double time2 = timer2.elapsedTime(); StdOut.printf("%e (%.2f seconds)\n", sum2, time2); }} /****************************************************************************** * Copyright 2002-2020, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/