4.1, 4.2 Performance and SortingRunning TimeCharles Babbage (1864)“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 BabbageAnalytic Enginehow many times do youhave to turn the crank?Algorithmic SuccessesN-body Simulation.•Simulate gravitational interactions among N bodies.•Brute force: N2 steps.number of bodies(N2)(N log N)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 number of bodies(N2)(N log N)Algorithmic SuccessesDiscrete Fourier transform.•Break down waveform of N samples into periodic components.•Applications: DVD, JPEG, MRI, astrophysics, ….•Brute force: N2 steps.Freidrich Gauss1805number of samples(N2)(N log N)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.John Tukey1965number of samples(N2)(N log N)SortingSortingSorting problem. Rearrange N items in ascending order.Applications. Binary search, statistics, databases, data compression, bioinformatics, computer graphics, scientific computing, (too numerous to list) ... HanleyHaskellHauserHayesHongHornetHsuHauserHongHsuHayesHaskellHanleyHornetInsertion SortInsertion sort.•Brute-force sorting solution.•Move left-to-right through array.•Insert each element into final position byexchanging it with larger elements to its left, one-by-one.Insertion Sortinsertion sort is simpler and faster than bubble sort,so we don’t teach bubble sort anymoreInsertion sort.•Brute-force sorting solution.•Move left-to-right through array.•Exchange next element with larger elements to its left, one-by-one.Insertion SortInsertion Sort: Java Implementationpublic class Insertion{ public static void sort(String[] a) { int N = a.length; for (int i = 1; i < N; i++) for (int j = i; j > 0; j--) if (a[j-1] > a[j]) exch(a, j-1, j); else break; } private static void exch(String[] a, int i, int j) { String swap = a[i]; a[i] = a[j]; a[j] = swap; }}Insertion Sort: ObservationObserve and tabulate running time for various values of N.Data source: N random numbers between 0 and 1.Machine: Apple G5 1.8GHz with 1.5GB memory running OS X.Timing: Skagen wristwatch.5.6 seconds400 million40,0001.5 seconds99 million20,0000.43 seconds25 million10,0000.13 seconds6.2 million5,00023 secondsTimeComparisonsN1600 million80,000Data analysis. Plot # comparisons vs. input size on log-log scale.Hypothesis. # comparisons grows quadratically with input size ~ N 2 / 4.Insertion Sort: Empirical Analysis1.00010.000100.0001000.00010000.000100000.0001000 10000 100000 1000000Comparsions (millions)Input Size Actual Fitted NorthslopeInsertion Sort: Empirical AnalysisObservation. Number of compares depends on input family.•Descending: ~ N 2 / 2.•Random: ~ N 2 / 4.•Ascending: ~ N.0.0010.0100.1001.00010.000100.0001000.00010000.000100000.0001000000.0001000 10000 100000 1000000Comparsions (millions)Input SizeDescendingRandomAscendingAnalysis: Empirical vs. MathematicalEmpirical 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.Insertion Sort: Mathematical AnalysisWorst case. [descending]•Iteration i requires i comparisons.•Total = (0 + 1 + 2 + ... + N-1) ~ N 2 / 2 compares.Average case. [random]•Iteration i requires i / 2 comparisons on average.•Total = (0 + 1 + 2 + ... + N-1) / 2 ~ N 2 / 4 comparesE F G H I J D C B AA C D F H J E B I GiiInsertion Sort: LessonLesson. Supercomputer can't rescue a bad algorithm.1 second1 dayMillioninstantinstantThousand BillionComparisons Per SecondComputer3 centuries107laptop2 weeks1012superMoore's LawMoore's law. Transistor density on a chip doubles every 2 years.Variants. Memory, disk space, bandwidth, computing power per $.http://en.wikipedia.org/wiki/Moore's_lawMoore's Law and AlgorithmsQuadratic algorithms do not scale with technology.•New computer may be 10x as fast.•But, has 10x as much memory so problem may be 10x bigger.•With quadratic algorithm, takes 10x as long!Lesson. Need linear (or linearithmic) algorithm to keep pace with Moore's law.“Software inefficiency can always outpace Moore's Law. Moore's Law isn't a match for our bad coding.” – Jaron LanierAnnouncementsExam 1 looms.Written exam Tuesday 3/13 during your lecture time. Room TBD.Programming exam Tuesday 3/13 or Wednesday 3/14 in your precept.Review session will be held.Rooms, rules, details on Exams page of website.MergesortMergesortMergesort.•Divide array into two halves.•Recursively sort each half.•Merge two halves to make sorted whole.Mergesort: ExampleMergingMerging. Combine two pre-sorted lists into a sorted whole.How to merge efficiently? Use an auxiliary array.waswaswasA G L O R H I M S T MergingMerge.•Keep track of smallest element in each sorted half.•Choose smaller of two elements.•Repeat until done.AA G L O R H I M S TA MergingMerge.•Keep track of smallest element in each sorted half.•Choose smaller of two elements.•Repeat until done.GA G L O R H I M S TA G MergingMerge.•Keep track of smallest element in each sorted half.•Choose smaller of two elements.•Repeat until done.HA G L O R H I M S TA G H MergingMerge.•Keep track of smallest element in each sorted half.•Choose smaller of two elements.•Repeat until done.IA G L O R H I M S TA G H I L M O R S TMergingMerge.•Keep track of smallest element in each sorted half.•Choose smaller of two elements.•Repeat until done.MergingMerging. Combine two pre-sorted lists into a sorted whole.How to merge efficiently? Use