Question? Leave a message!




Reasons to Analyze Algorithms

Reasons to Analyze Algorithms
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
4.1 Performance Introduction to Programming in Java: An Interdisciplinary Approach · Robert Sedgewick and Kevin Wayne · Copyright © 2002–2010 · 6/26/10 8:05 AM Running Time “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 Babbage how many times do you have to turn the crank? Charles Babbage (1864) Analytic Engine 2 The Challenge Q. Will my program be able to solve a large practical problem? compile debug on solve problems test case in practice Key insight. Knuth 1970s Use the scientific method to understand performance. 3 Scientific Method Scientific method.   Observe some feature of the natural world.   Hypothesize a model that is consistent with the observations.   Predict events using the hypothesis.   Verify the predictions by making further observations.   Validate by repeating until the hypothesis and observations agree. Principles.   Experiments we design must be reproducible.   Hypothesis must be falsifiable. 4 Reasons to Analyze Algorithms Predict performance.   Will my program finish?   When will my program finish? Compare algorithms.   Will this change make my program faster?   How can I make my program faster? Basis for inventing new ways to solve problems.   Enables new technology.   Enables new research. 5 Algorithmic Successes Discrete Fourier transform.   Break down waveform of N samples into periodic components.   Applications: DVD, JPEG, MRI, astrophysics, …. 2   Brute force: N steps. Freidrich Gauss 1805   FFT algorithm: N log N steps, enables new technology. 6 Algorithmic Successes N-body Simulation.   Simulate gravitational interactions among N bodies. 2   Brute force: N steps.   Barnes-Hut: N log N steps, enables new research. Andrew Appel PU '81 7 Three-Sum Problem Three-sum problem. Given N integers, find triples that sum to 0. Context. Deeply related to problems in computational geometry. % more 8ints.txt 30 -30 -20 -10 40 0 10 5 % java ThreeSum 8ints.txt 4 30 -30 0 30 -20 -10 -30 -10 40 -10 0 10 Q. How would you write a program to solve the problem? 8 Three-Sum: Brute-Force Solution public class ThreeSum // return number of distinct triples (i, j, k) // such that (ai + aj + ak == 0) public static int count(int a) int N = a.length; all possible triples i j k 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 (ai + aj + ak == 0) cnt++; return cnt; public static void main(String args) int a = StdArrayIO.readInt1D(); StdOut.println(count(a)); 9 Empirical Analysis Empirical Analysis Empirical analysis. Run the program for various input sizes. † N time 512 0.03 1024 0.26 2048 2.16 4096 17.18 8192 136.76 † Running Linux on Sun-Fire-X4100 with 16GB RAM 11 Stopwatch Q. How to time a program? A. A stopwatch. 12 Stopwatch Q. How to time a program? A. A Stopwatch object. public class Stopwatch private final long start; public Stopwatch() start = System.currentTimeMillis(); public double elapsedTime() return (System.currentTimeMillis() - start) / 1000.0; 13 Stopwatch Q. How to time a program? A. A Stopwatch object. public static void main(String args) int a = StdArrayIO.readInt1D(); Stopwatch timer = new Stopwatch(); StdOut.println(count(a)); StdOut.println(timer.elapsedTime()); 14 Empirical Analysis Data analysis. Plot running time vs. input size N. Q. How fast does running time grow as a function of input size N ? 15 Empirical Analysis b Initial hypothesis. Running time obeys power law f (N) = a N . Data analysis. Plot running time vs. input size N on a log-log scale. slope = 3 Consequence. Power law yields straight line (slope = b). slope 3 Refined hypothesis. Running time grows as cube of input size: a N . 16 Doubling Hypothesis Doubling hypothesis. Quick way to estimate b in a power law hypothesis. Run program, doubling the size of the input? † N time ratio 512 0.033- 1024 0.26 7.88 2048 2.16 8.43 4096 17.18 7.96 8192 136.76 7.96 seems to converge to a constant c = 8 b Hypothesis. Running time is about a N with b = lg c. 17 Performance Challenge 1 Let F(N) be running time of main() as a function of input N. public static void main(String args) ... int N = Integer.parseInt(args0); ... Scenario 1. F(2N) / F(N) converges to about 4. Q. What is order of growth of the running time? 18 Performance Challenge 2 Let F(N) be running time of main() as a function of input N. public static void main(String args) ... int N = Integer.parseInt(args0); ... Scenario 2. F(2N) / F(N) converges to about 2. Q. What is order of growth of the running time? 19 Prediction and Validation 3 Hypothesis. Running time is about a N for input of size N. Q. How to estimate a? † N time A. Run the program 4096 17.18 3 17.17 = a 4096 –10 4096 17.15 ⇒ a = 2.5 × 10 4096 17.17 –10 3 Refined hypothesis. Running time is about 2.5 × 10 × N seconds. Prediction. 1,100 seconds for N = 16,384. Observation. † N time validates hypothesis 16384 1118.86 20