Question? Leave a message!




Reasons to Analyze Algorithms

Reasons to Analyze Algorithms
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 Nbody Simulation.   Simulate gravitational interactions among N bodies. 2   Brute force: N steps.   BarnesHut: N log N steps, enables new research. Andrew Appel PU '81 7 ThreeSum Problem Threesum 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 ThreeSum: BruteForce 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 SunFireX4100 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 loglog 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 Mathematical Analysis Donald Knuth Turing award '74 Mathematical Analysis Running time. Count up frequency of execution of each instruction and weight by its execution time. int count = 0; for (int i = 0; i N; i++) if (ai == 0) count++; operation frequency variable declaration 2 variable assignment 2 less than comparison N + 1 between N (no zeros) equal to comparison N and 2N (all zeros) array access N increment ≤ 2 N 22 Mathematical Analysis Running time. Count up frequency of execution of each instruction and weight by its execution time. int count = 0; for (int i = 0; i N; i++) for (int j = i+1; j N; j++) if (ai + aj == 0) count++; operation frequency 0 + 1 + 2 + ... + (N−1) = 1/2 N(N−1) variable declaration N + 2 variable assignment N + 2 € less than comparison 1/2 (N + 1) (N + 2) equal to comparison 1/2 N (N – 1) becoming very tedious to count array access N (N – 1) 2 increment ≤ N 23 Tilde Notation Tilde notation.   Estimate running time as a function of input size N.   Ignore lower order terms. –  when N is large, terms are negligible –  when N is small, we don't care 3 2 3 Ex 1. 6 N + 17 N + 56 6 N 3 4/3 3 Ex 2. 6 N + 100 N + 56 6 N 3 2 3 Ex 3. 6 N + 17 N log N 6 N discard lowerorder terms (e.g., N = 1000: 6 trillion vs. 169 million) f (N) lim = 1 Technical definition. f(N) g(N) means N→∞ g(N) 24 € Mathematical Analysis Running time. Count up frequency of execution of each instruction and weight by its execution time. Inner loop. Focus on instructions in "inner loop." 25 Constants in Power Law b Power law. Running time of a typical program is a N . Exponent b depends on: algorithm. Leading constant a depends on:   Algorithm. system independent effects   Input data.   Caching.   Machine.   Compiler. system dependent effects   Garbage collection.   Justintime compilation.   CPU use by other applications. Our approach. Use doubling hypothesis (or mathematical analysis) to estimate exponent b, run experiments to estimate a. 26 Analysis: Empirical vs. Mathematica l Empirical analysis.   Measure running times, plot, and fit curve.   Easy to perform experiments.   Model useful for predicting, but not for explaining. Mathematical analysis.   Analyze algorithm to estimate ops as a function of input size.   May require advanced mathematics.   Model useful for predicting and explaining. Critical difference. Mathematical analysis is independent of a particular machine or compiler; applies to machines not yet built. 27 Order of Growth Classifications Observation. A small subset of mathematical functions suffice to describe running time of many fundamental algorithms. while (N 1) public static void g(int N) N = N / 2; if (N == 0) return; ... g(N/2); g(N/2); for (int i = 0; i N; i++) lg N ... lg N = log N 2 N lg N for (int i = 0; i N; i++) ... N public static void f(int N) if (N == 0) return; f(N1); for (int i = 0; i N; i++) f(N1); for (int j = 0; j N; j++) ... ... 2 N N 2 28 Order of Growth Classifications 29 Order of Growth: Consequences 30 Dynamic Programming Binomial Coefficients ⎛ ⎞ n = Binomial coefficient. ⎜ ⎟ number of ways to choose k of n elements. k ⎝ ⎠ ⎛ ⎞ 52 Ex. Number of possible 7card poker hands = = 2,598,960. € ⎜ ⎟ 7 ⎝ ⎠ € Ex. Probability of "quads" in Texas hold 'em: ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 13 4 48 × ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 1 4 3 224,848 ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ = (about 594 :1) ⎛ ⎞ 52 133,784,560 ⎜ ⎟ 7 ⎝ ⎠ € 32 Binomial Coefficients ⎛ ⎞ n = Binomial coefficient. ⎜ ⎟ number of ways to choose k of n elements. k ⎝ ⎠ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ n n−1 n−1 = + ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ Pascal's identity. € k k−1 k ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ contains excludes first element first element € Pascal's triangle. 33 Binomial Coefficients: Sierpinski Triangle ⎛ ⎞ n = Binomial coefficient. ⎜ ⎟ number of ways to choose k of n elements. k ⎝ ⎠ Sierpinski triangle. Color black the odd integers in Pascal's triangle. € 34 Binomial Coefficients: First Attempt public class SlowBinomial // natural recursive implementation public static long binomial(long n, long k) if (k == 0) return 1; if (n == 0) return 0; return binomial(n1, k1) + binomial(n1, k); public static void main(String args) int N = Integer.parseInt(args0); Pascal’s identity int K = Integer.parseInt(args1); StdOut.println(binomial(N, K)); 35 Performance Challenge 3 Q. Is this an efficient way to compute binomial coefficients A. No, no, no same essential recomputation flaw as naïve Fibonacci (6, 4) (5, 4) (5, 3) recomputed twice (4, 4) (4, 3) (4, 3) (4, 2) (3, 3) (3, 2) (3, 3) (3, 2) (3, 2) (3, 1) (2, 2) (2, 1) (2, 2) (2, 1) (2, 2) (2, 1) (2, 1) (3, 0) (1, 1) (1, 0) (1, 1) (1, 0) (1, 1) (1, 0) (1, 1) (1, 0) 36 Timing Experiments Timing experiments: direct recursive solution. † (2N, N) time (26, 13) 0.46 (28, 14) 1.27 (30, 15) 4.30 increase N by 1, running time increases by about 4x (32, 16) 15.69 (34, 17) 57.40 (36, 18) 230.42 Q. Is running time linear, quadratic, cubic, exponential in N 37 Performance Challenge 4 Let F(N) be running time to compute binomial(2N, N). public static long binomial(long n, long k) if (k == 0) return 1; if (n == 0) return 0; return binomial(n1, k1) + binomial(n1, k); Observation. F(N+1) / F(N) converges to about 4. Q. What is order of growth of the running time N will not finish unless N is small A. Exponential: a 4 . 38 Dynamic Programming Key idea. Save solutions to subproblems to avoid recomputation. k 0 1 2 3 4 0 1 0 0 0 0 1 1 1 0 0 0 2 1 2 1 0 0 n 3 1 3 3 1 0 4 1 4 6 4 1 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ n n−1 n−1 = + 5 1 5 10 10 5 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ k k−1 k ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 6 1 6 15 20 15 20 = 10 + 10 € binomial(n, k) Tradeoff. Trade (a little) memory for (a huge amount of) time. 39 Binomial Coefficients: Dynamic Programming public class Binomial public static void main(String args) int N = Integer.parseInt(args0); int K = Integer.parseInt(args1); long bin = new longN+1K+1; // base cases for (int k = 1; k = K; k++) bin0K = 0; for (int n = 0; n = N; n++) binN0 = 1; // bottomup dynamic programming for (int n = 1; n = N; n++) for (int k = 1; k = K; k++) binnk = binn1k1 + binn1k; // print results StdOut.println(binNK); 40 Timing Experiments Timing experiments for binomial coefficients via dynamic programming. † (2N, N) time (26, 13) instant (28, 14) instant (30, 15) instant (32, 16) instant (34, 17) instant (36, 18) instant Q. Is running time linear, quadratic, cubic, exponential in N 41 Performance Challenge 5 Let F(N) be running time to compute binomial(2N, N) using DP. for (int n = 1; n = N; n++) for (int k = 1; k = K; k++) binnk = binn1k1 + binn1k; Q. What is order of growth of the running time 2 effectively instantaneous for small N A. Quadratic: a N . N 2 Remark. There is a profound difference between 4 and N . cannot solve can solve a large problem a large problem 42 Digression: Stirling's Approximation ⎛ ⎞ n n Alternative: = ⎜ ⎟ k k (n−k) ⎝ ⎠ Caveat. 52 overflows a long, even though final result doesn't. € Instead of computing exact values, use Stirling's approximation: ln(2πn) 1 1 1 lnn ≈ n lnn − n + + − + 3 5 2 12n 360n 1260n € Application. Probability of exact k heads in n flips with a biased coin. ⎛ ⎞ n k n−k p (1− p) ⎜ ⎟ (easy to compute approximate value with Stirling's formula) k ⎝ ⎠ 43 € Memory Typical Memory Requirements for Java Data Types Bit. 0 or 1. Byte. 8 bits. 10 Megabyte (MB). 1 million bytes 2 bytes. 20 Gigabyte (GB). 1 billion bytes 2 bytes. typical computer ’10 has about 2GB memory Q. What's the biggest double array you can store on your computer 45 Performance Challenge 6 Q. How much memory does this program require as a function of N public class RandomWalk public static void main(String args) int N = Integer.parseInt(args0); int count = new intNN; int x = N/2; int y = N/2; for (int i = 0; i N; i++) // no new variable declared in loop ... countxy++; A. 46 Summary Q. How can I evaluate the performance of my program A. Computational experiments, mathematical analysis, scientific method. Q. What if it's not fast enough Not enough memory   Understand why.   Buy a faster computer.   Learn a better algorithm (COS 226, COS 423).   Discover a new algorithm. attribute better machine better algorithm cost or more or less makes "everything" does not apply to applicability run faster some problems quantitative dramatic qualitative improvement improvements improvements possible 47
Website URL
Comment