COMPUTER SC I ENCE S E D G E W I C K / W A Y N E

PART I : PROGRAMMIN G IN JAVA

http://introcs.cs.princeton.edu

R O B E R T S E D G E W I C K K E V I N W A Y N E

C om

puter Science

ComputerScience An Interdisciplinary Approach

7. Performance

Section 4.1

7. Performance

•The challenge •Empirical analysis •Mathematical models •Doubling method •Familiar examples

COMPUTER SC I ENCE S E D G E W I C K / W A Y N E

PART I : PROGRAMMIN G IN JAVA

CS.7.A.Performance.Challenge

3

The challenge (since the earliest days of computing machines)

Difference Engine #2

Designed by Charles Babbage, c. 1848

Built by London Science Museum, 1991

“ 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

Q. How many times do you
 have to turn the crank?

The challenge (modern version)

4

Q. Will I be able to use my program to solve a large practical problem?

Key insight (Knuth 1970s). Use the scientific method to understand performance.

Q. If not, how might I understand its performance characteristics so as to improve it?

5

Three reasons to study program performance

2. To compare algorithms and implementations.

• Will this change make my program faster? • How can I make my program faster?

3. To develop a basis for understanding the
 problem and for designing new algorithms

• Enables new technology.

• Enables new research.

1. To predict program behavior

• Will my program finish? • When will my program finish?

public class Gambler { public static void main(String[] args) { int stake = Integer.parseInt(args[0]); int goal = Integer.parseInt(args[1]); int trials = Integer.parseInt(args[2]); int wins = 0; for (int t = 0; t < trials; t++) { int cash = stake; while (cash > 0 && cash < goal) if (Math.random() < 0.5) cash++;
 else cash–; if (cash == goal) wins++; } StdOut.print(wins + ” wins of ” + trials); } }

An algorithm is a method for solving a problem that is

suitable for implementation as a computer program.

We study several algorithms later in this course.
 Taking more CS courses? You’ll learn dozens of algorithms.

An algorithm design success story

N-body simulation

• Goal: Simulate gravitational interactions among N bodies. • Brute-force algorithm uses N 2 steps per time unit. • Issue (1970s): Too slow to address scientific problems of interest. • Success story: Barnes-Hut algorithm uses N logN steps and enables new research.

6

problem size (N )

ti m

e

N 2

N logN

limit on available time

Andrew Appel PU ’81

senior thesis

Another algorithm design success story

Discrete Fourier transform

• Goal: Break down waveform of N samples into periodic components. • Applications: digital signal processing, spectroscopy, … • Brute-force algorithm uses N 2 steps. • Issue (1950s): Too slow to address commercial applications of interest. • Success story: FFT algorithm uses N logN steps and enables new technology.

7

problem size (N )

ti m

e

N 2

N logN

limit on available time

John Tukey 1915–2000

Quick aside: binary logarithms

8

Def. The binary logarithm of a number N (written lg N )
 is the number x satisfying 2x = N.

N approximate value lgN log10N

210 1 thousand 10 3.01

220 1 million 20 6.02

230 1 billion 30 9.03

Frequently encountered values

Fact. The number of bits in the binary representation of N is 1+⎣lg N⎦.

Q. How many recursive calls for convert(N)?

Fact. Binary logarithms arise in the study of algorithms based on recursively solving problems 
 half the size (divide-and-conquer algorithms), like convert, FFT and Barnes-Hut.

A. Largest integer less than or equal to lg N (written ⎣lg N⎦).

public static String convert(int N) { if (N == 1) return “1”; return convert(N/2) + (N % 2); }

N

lg N

1 2 4 8 16

2

4

0 1

3

Prove by induction. Details in “sorting and searching” lecture.

or log2N

An algorithmic challenge: 3-sum problem

Three-sum. Given N integers, enumerate the triples that sum to 0.

9

Q. Can we solve this problem for N = 1 million?

Applications in computational geometry

• Find collinear points.

• Does one polygon fit inside another?

• Robot motion planning.