CS计算机代考程序代写 data structure c/c++ algorithm 04_Measuring_Performance_and_Analysis

04_Measuring_Performance_and_Analysis

Data Structures & Algorithms

Measuring Runtime Performance

Complexity Notation
• n = input size
• f(n) = max number of steps when input has size n
• O(f(n)) = asymptotic upper bound

1 void f(int *out, const int *in, int size) {

2 int product = 1;

3 for (int i = 0; i < size; ++i) 4 product *= in[i]; 5 for(int i = 0; i < size; ++i) 6 out[i] = product / in[i]; 7 } // f() f(n) = 1 + 1 + 1 + 3n + 1 + 1 + 3n = 6n + 5 = O(n) 2 Ways to measure complexity • Analytically – Analysis of the code itself – Recognizing common algorithms/patterns – Based on a recurrence relation • Empirically – Measure runtime programmatically – Measure runtime using external tools – Test on inputs of a variety of sizes 3 Measuring Runtime Programmatically • "Programmatically" – measurements are taken from inside the code itself • Varies greatly depending on the language • Many different ways to do it even just in C/C++! 4 1 #include
2
3 class Timer {
4 std::chrono::time_point cur;
5 std::chrono::duration elap;
6 public:
7 Timer() : cur(), elap(std::chrono::duration::zero()) {}
8
9 void start() {
10 cur = std::chrono::system_clock::now();
11 } // start()
12
13 void stop() {
14 elap += std::chrono::system_clock::now() – cur;
15 } // stop()
16
17 void reset() {
18 elap = std::chrono::duration::zero();
19 } // reset()
20
21 double seconds() {
22 return elap.count();
23 } // seconds()
24 }; // Timer{}

25 int main() {
26 Timer t;
27 t.start();
28 doStuff1();
29 t.stop();
30 cout << "1: " << t.seconds() 31 << "s" << endl; 32 33 t.reset(); 34 t.start(); 35 doStuff2(); 36 t.stop(); 37 cout << "2: " << t.seconds() 38 << "s" << endl; 39 return 0; 40 } // main() Measuring Time In C++11+ Example Credit: Amir Kamil Note: Checking time too often will slow down your program! 5 Let's try it! From a web browser: goo.gl/gONvC0 (lower g, capital ON, lower v, capital C, zero) From a terminal: wget goo.gl/gONvC0 -O search.cpp 6 After Downloading • If you haven’t already, add this to your .bash_profile: module load gcc/6.2.0 • Compile: g++ -std=c++1z -O3 search.cpp -o search • Run a binary search, 1M items: ./search b 1000000 • Run a linear search, 1M items: ./search l 1000000 • Try with larger numbers! 7 • Plot actual run time versus varying input sizes • Include a large range to accurately display trend • Caveat: for small inputs, asymptotics may not play out yet Empirical Results Algorithm A looks linear Algorithm A no longer looks linear 8 Prediction versus Experiment • What if experimental results are worse than predictions? – Example: results are exponential when analysis is linear – Error in complexity analysis – Error in coding (check for extra loops, unintended operations, etc.) • What if experimental results are better than predictions? – Example: results are linear when analysis is exponential – Experiment may not have fit worst case scenario – Error in complexity analysis – Error in analytical measurements – Incomplete algorithm implementation – Algorithm implemented is better than the one analyzed • What if experimental data match asymptotic prediction but runs are too slow? – Performance bug? – Check compile options (e.g. use -O3) – Look for optimizations to improve the constant factors 9 Data Structures & Algorithms Measuring Runtime Performance Data Structures & Algorithms Runtime Analysis Tools Using a Profiling Tool • This won't tell you the complexity of an algorithm, but it tells you where you program spends its time. • Many different tools exist – you'll learn to use perf in lab. A snapshot of a perf report generated for EECS 280 Project 2. Image credit: Alexandra Brown 12 Measuring Runtime on Linux If you are launching a program using command % progName –options args Then % /usr/bin/time progName –options args will produce a runtime report 0.84user 0.00system 0:00.85elapsed 99%CPU If you’re timing a program in the current folder, use ./ % /usr/bin/time ./progName –options args Often, you can just type time rather than /usr/bin/time. 13 Measuring Runtime on Linux • Example: this command just wastes time by copying zeros to the "bit bucket” % time dd if=/dev/zero of=/dev/null kill it with control-C 3151764+0 records in 3151764+0 records out 1613703168 bytes (1.6 GB) copied, 0.925958 s, 1.7 GB/s Command terminated by signal 2 0.26user 0.65system 0:00.92elapsed 99%CPU (0avgtext+0avgdata 3712maxresident)k 0inputs+0outputs (0major+285minor)pagefaults 0swaps 14 Measuring Runtime on Linux 0.26user 0.65system 0:00.92elapsed 99%CPU • user time is spent by your program • system time is spent by the OS on behalf of your program • elapsed is wall clock time - time from start to finish of the call, including any time slices used by other processes • %CPU Percentage of the CPU that this job got. This is just (user + system) / elapsed • man time for more information 15 Using valgrind • Suppose we want to check for memory leaks: valgrind ./search b 1000000 • Force a leak! – Replace return 0 with exit(0), run valgrind using flags --leak-check=full --show-leak-kinds=all • Who leaked that memory? – The memory address isn’t very useful, we just know that main() called operator new – Recompile with -g3 instead of -O3 and run valgrind one more time 16 Data Structures & Algorithms Runtime Analysis Tools Data Structures & Algorithms Analyzing Recursion Job Interview Question • Implement this function // returns x^n int power(int x, uint32_t n); • The obvious solution uses n - 1 multiplications – 28 = 2*2* ... *2 • Less obvious: O(log n) multiplications – Hint: 28 = ((22)2)2 – How does it work for 27? • Write both solutions iteratively and recursively 19 Computing xn 1 int power(int x, uint32_t n) { 2 if (n == 0) { 3 return 1; 4 } // if 5 6 int result = x; 7 for (int i = 1; i < n; ++i) { 8 result = result * x; 9 } // for 10 11 return result; 12 } // power() 20 Analyzing Solutions Iterative 1 int power(int x, int n) { 2 int result = 1; 3 for (int i = 0; i < n; ++i) { 4 result = result * x; 5 } // for() 6 7 return result; 8 } // power() Recursive 9 int power(int x, int n) { 10 if (n == 0) { 11 return 1; 12 } // if() 13 return x * power(x, n - 1); 14 } // power() • Iterative functions use loops • A function is recursive if it calls itself • What is the time complexity of each function? Θ(n) It's just a regular loop. ??? We need another tool to analyze this. 21 Recurrence Relations • A recurrence relation describes the way a problem depends on a subproblem. – A recurrence can be written for a computation: – A recurrence can be written for the time taken: – A recurrence can be written for the amount of memory used*: *Non-tail recursive 22 𝑇 𝑛 = $ 𝑐! 𝑇 𝑛 − 1 + 𝑐" 𝑛 == 0 𝑛 > 0

𝑥# = $ 1
𝑥 ∗ 𝑥#$”

𝑛 == 0
𝑛 > 0

𝑀 𝑛 = $
𝑐!

𝑀 𝑛 − 1 + 𝑐”
𝑛 == 0
𝑛 > 0

Solving Recurrences

• Substitution method
1. Write out T(n), T(n – 1), T(n – 2)
2. Substitute T(n – 1), T(n – 2) into T(n)
3. Look for a pattern
4. Use a summation formula

• Another way to solve recurrence equations
is the Master Method (AKA Master
Theorem)

• Recursion tree method
23

Solving Recurrences: Linear
1 int power(int x, int n) {

2 if (n == 0)

3 return 1;

4

5 return x * power(x, n – 1);

6 } // power()

24

𝑇 𝑛 = $
𝑐!

𝑇 𝑛 − 1 + 𝑐”
𝑛 == 0
𝑛 > 0

Recurrence: T(n) = T(n – 1) + c
Complexity: Θ(n)

Solving Recurrences: Logarithmic
1 int power(int x, int n) {

2 if (n == 0)

3 return 1;

4

5 int result = power(x, n / 2);

6 result *= result;

7 if (n % 2 != 0) // n is odd
8 result *= x;

9

10 return result;

11 } // power()

25

𝑇 𝑛 = +
𝑐!

𝑇
𝑛
2
+ 𝑐”

𝑛 == 0
𝑛 > 0

Recurrence: T(n) = T(n / 2) + c
Complexity: Θ(log n)

A Logarithmic Recurrence Relation

• Fits the logarithmic recursive implementation of
power()
– The power to be calculated is divided into two halves

and combined with a single multiplication
• Also fits Binary Search

– The search space is cut in half each time, and the
function recurses into only one half

à

26

Θ(log 𝑛)𝑇 𝑛 = +
𝑐!

𝑇
𝑛
2
+ 𝑐”

𝑛 == 0

𝑛 > 0

Recurrence Thought Exercises

• What if a recurrence cuts a problem into two
subproblems, and both subproblems were
recursively processed?

• What if a recurrence cuts a problem into three
subproblems and…
– Processes one piece
– Processes two pieces
– Processes three pieces

• What if there was additional, non-constant work
after the recursion?

27

Binomial Coefficient

• Binomial Coefficient – “n choose k”
• Write this function with pen and paper
• Compile and test what you’ve written
• Options

– Iterative
– Recursive
– Tail recursive

• Analyze
28

𝑛
𝑘 =

𝑛!
𝑘! 𝑛 − 𝑘 !

Data Structures & Algorithms

Analyzing Recursion