Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 22, 2010 10:11:28 AM‣estimating running time‣mathematical analysis‣order-of-growth hypotheses‣input models‣measuring space1.4 Analysis of AlgorithmsReference: Intro to Programming in Java, Section 4.1Cast of characters2Programmer needs to developa working solution.Client wants problemsolved efficiently.Theoretician wants to understand.Basic blocking and tacklingis sometimes necessary.[this lecture]Student might play anyor all of these rolessomeday.3Running timeCharles Babbage (1864) Analytic Enginehow many times do you have to turn the crank?“ As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise—By what course of calculation can these results be arrived at by the machine in the shortest time? ” — Charles BabbagePredict performance.Compare algorithms.Provide guarantees.Understand theoretical basis.Primary practical reason: avoid performance bugs. Reasons to analyze algorithms4this course (COS 226)theory of algorithms (COS 423)client gets poor performance because programmerdid not understand performance characteristics5Some algorithmic successesDiscrete Fourier transform.•Break down waveform of N samples into periodic components.•Applications: DVD, JPEG, MRI, astrophysics, ….•Brute force: N2 steps.•FFT algorithm: N log N steps, enables new technology.Friedrich Gauss1805Linear, linearithmic, and quadratic8T16T32T64Ttime1K 2K 4K 8Ksizequadraticlinearithmiclinear6Some algorithmic successesN-body Simulation.•Simulate gravitational interactions among N bodies.•Brute force: N2 steps.•Barnes-Hut: N log N steps, enables new research.Andrew AppelPU '81 Linear, linearithmic, and quadratic8T16T32T64Ttime1K 2K 4K 8Ksizequadraticlinearithmiclinear7‣estimating running time‣mathematical analysis‣order-of-growth hypotheses‣input models‣measuring space8Scientific analysis of algorithmsA framework for predicting performance and comparing algorithms.Scientific method.•Observe some feature of the universe.•Hypothesize a model that is consistent with observation.•Predict events using the hypothesis.•Verify the predictions by making further observations.•Validate by repeating until the hypothesis and observations agree.Principles.•Experiments must be reproducible.•Hypotheses must be falsifiable.Universe = computer itself.Every time you run a program you are doing an experiment!First step. Debug your program!Second step. Choose input model for experiments.Third step. Run and time the program for problems of increasing size.Why is my program so slow ??Experimental algorithmics910Example: 3-sum3-sum. Given N integers, find all triples that sum to exactly zero.Context. Deeply related to problems in computational geometry.% more input8.txt8 30 -30 -20 -10 40 0 10 5% java ThreeSum < input8.txt 4 30 -30 0 30 -20 -10-30 -10 40-10 0 10public class ThreeSum{ public static int count(int[] a) { int N = a.length; int cnt = 0; for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) for (int k = j+1; k < N; k++) if (a[i] + a[j] + a[k] == 0) cnt++; return cnt; } public static void main(String[] args) { long[] a = StdArrayIO.readInt1D(); StdOut.println(count(a)); }} 113-sum: brute-force algorithmcheck each tripleignore overflowRun the program for various input sizes and measure running time.12Empirical analysisNtime (seconds) †10000.2620002.16400017.188000137.76† Running Linux on Sun-Fire-X4100ThreeSum.javaQ. How to time a program?A. Manual.13Measuring the running timeQ. How to time a program?A. Automatic.14Measuring the running timeclient codeimplementation (part of stdlib.jar, see http://www.cs.princeton.edu/introcs/stdlib)Stopwatch stopwatch = new Stopwatch();ThreeSum.count(a);double time = stopwatch.elapsedTime();StdOut.println("Running time: " + time + " seconds");public class Stopwatch { private final long start = System.currentTimeMillis(); public double elapsedTime() { long now = System.currentTimeMillis(); return (now - start) / 1000.0; }}Plot running time as a function of input size N.15Data analysis16Log-log plot. Plot running time vs. input size N on log-log scale.Regression. Fit straight line through data points: a N b.Hypothesis. Running time grows with the cube of the input size: a N 3.Data analysisslopepower lawslope = 3Doubling hypothesis. Quick way to estimate b in a power law hypothesis.Run program, doubling the size of the input.Hypothesis. Running time is about a N b with b = lg ratio. Caveat. Can't identify logarithmic factors with doubling hypothesis.17Doubling hypothesisNtime (seconds) †ratiolg ratio5000.03-1,0000.267.882.982,0002.168.433.084,00017.187.962.998,000137.767.962.99seems to converge to a constant b ! 318Prediction and verificationHypothesis. Running time is about a N 3 for input of size N.Q. How to estimate a?A. Run the program!Refined hypothesis. Running time is about 2.7 ! 10 –10 ! N 3 seconds.Prediction. 1,100 seconds for N = 16,000.Observation.validates hypothesis!Ntime (seconds)4,00017.184,00017.154,00017.17Ntime (seconds)163841118.8617.17 = a ! 40003" a = 2.7 ! 10 –1019Experimental algorithmicsMany obvious factors affect running time:•Machine.•Compiler.•Algorithm.•Input data.More factors (not so obvious):•Caching.•Garbage collection.•Just-in-time compilation.•CPU use by other applications.Bad news. It is often difficult to get precise measurements.Good news. Easier than other sciences.e.g., can run huge number of experiments20War story (from COS 126)Q. How long does this program take as a function of N?Jenny. ~ c1 N2 seconds.Kenny. ~ c2 N seconds.public class EditDistance{ String s = StdIn.readString(); int N = s.length(); ... for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) distance[i][j] = ... ...} Ntime1,0000.112,0000.354,0001.68,0006.5Ntime2500.55001.11,0001.92,0003.9JennyKenny21‣estimating running time‣mathematical analysis‣order-of-growth hypotheses‣input models‣measuring space22Mathematical models for running timeTotal running time: sum of cost ! frequency for all operations.•Need to analyze program to determine set of operations.•Cost depends on machine,
View Full Document
Unlocking...