performance analysis

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

By: karthikarthick (31 month(s) ago)

send soon

By: karthikarthick (31 month(s) ago)

pls sir

By: karthikarthick (31 month(s) ago)

pls sir

By: karthikarthick (31 month(s) ago)

Hello sir plz give me permission to download this ppt

By: fathysalem (37 month(s) ago)

thanks...important one for me

See all

Presentation Transcript

UNIT-1 : 

UNIT-1 Chapter-2 Performance analysis

Slide 2: 

CONTENTS 1. WHAT IS PERFORMANCE ANALYSIS 2. SPACE COMPLEXITY 2.1. components of space complexity 2.2. example 3. TIME COMPLEXITY 3.1. components of time complexity 3.2. operation counts 3.3. best, worst and average operation counts 3.4. step counts

Slide 3: 

Performance Analysis (machine independent) space complexity: storage requirement time complexity: computing time Performance Measurement (machine dependent)

1. WHAT IS PERFORMANCE ANALYSIS : 

1. WHAT IS PERFORMANCE ANALYSIS Performance of a program - amount of computer memory and time needed to run a program. Approaches - two approaches to determine the performance of a program 1. Analytical (or) Performance analysis - use analytical methods 2. Experimental (or) performance measurement - its measured by conducting experiments Space complexity - is the amount of memory needed to run and completion of a program.

Slide 5: 

Reason for space complexity (i) program run on multi-computer system amount of memory allocated to the program (ii) for any computer know whether (or) not sufficient memory to run the program (iii) a problem have several possible different space requirement specify available with

Slide 6: 

Example - one java compiler of your computer need only 1-MB of memory. - another need 4.MB of memory - 1.MB compiler is the only choice, if your computer has less than 4.MB of memory. - computer have extra memory will prefer smaller compiler, even it’s capabilities are comparable to bigger compiler. (iv) Space complexity is used to estimate the size if the largest problem, that a problem can solve.

Slide 7: 

Time complexity - amount of computer time needed to run and completion of a program. Reason for Time complexity 1. some computer system requires users to provide an upper limit on the amount of time, the program will run. - once this upper limit is reached the program is aborted. - the solution is: provide a time limit 2. The program developed user by satisfactory real-time response provide

Slide 8: 

Example: (a) A text editor takes a minute to move the cursor from one page down (or) up - is acceptable by many users. (b) A spread sheet program takes several minutes to re- evaluate the cell in a sheet - is satisfactory by few users. * (i.e) from the time-complexity of the program module: - we can decide whether (or) not the response time will be acceptable. * if it’s not acceptable then - redesign the algorithm (or) - give faster computer to user

2. SPACE COMPLEXITY : 

2. SPACE COMPLEXITY 2.1.Components of space complexity the space needed by a program has following components (a) Instruction space (b) Data space (c) Environment stack space (a) Instruction space - is the space needed to store the compiled version of the program instructions. - the amount of instruction space needed is depends on following factors: (i) the compiler used to compile the program into machine code. (ii) the compiler option – at the time of compilation. (iii) the target of computer.

Slide 10: 

- the compiler is a very important factor in determining - how much space the resulting code needed. Example: consider the following formula. a + b + b * c + ( a + b - c) / ( a + b) + 4 - it’s evaluated in three possible code as follows: (next slide) - these codes need a different amount of space & the compiler determine exactly which code will be generated. (e.g.) compiler provide optimization options to users. 1. code-optimization 2. execution-time optimization - the code in (b) is generated in non-optimization mode (refer next slide)

Slide 11: 

LOAD a LOAD a LOAD a ADD b ADD b ADD b STORE t1 STORE t1 STORE t1 LOAD b SUB c SUB c MULT c DIV t1 DIV t1 STORE t2 STORE t2 STORE t2 LOAD t1 LOAD b LOAD b ADD t2 MUL c MUL c STORE t3 STORE t3 ADD t2 LOAD a LOAD t1 ADD t1 ADD b ADD t3 ADD t4 SUB c ADD t2 STORE t4 ADD 4 (c) LOAD a ADD b (b) STORE t5 LOAD t4 DIV t5 where: t1,t2,-----t6 STORE t6 temporary variable needed for space LOAD t3 ADD t6 ADD 4 (a) program-1

Slide 12: 

- the code in (C) is generated in optimization mode & the code is shorter & time efficient. - use of optimization mode -- increase the time needed to compile the program - the configuration of the target computer affect the size of compiled code. (b) Data Space 1. Data space is the space needed to store all constant & variable values. 2. components of data space (a) space needed by constant and simple variables (b) space needed by dynamically allocated objects (e.g) Arrays , class

Slide 13: 

3. java language specifies the space allocated for simple variables and constants. (e.g) space requirement of an array is calculated as follows: = array size * space needed for a single array element double[ ] a = new double[ 100 ] int[ ] [ ] maze = new int[rows] [ cols] => when computing the space allocated to an array ignore calculating space allocated to store array size & type. double[ ] a = new double[100]; the array ‘a’ has space for 100 elements of type double [1-byte = 8-bits] i.e. 100 * 8 = 800 bytes

Slide 14: 

int[ ] [ ] maze = new int [rows] [cols] i.e. total space taken by this array = 4 * rows * cols (bytes) (C) Environment stack - it save the information which is needed to resume the execution of partially completed methods. - when each time a method is invoked the following data are saved on the environment stack. (i) return address (ii) values of all local variables & formal parameter in the method are invoked.

3. TIME COMPLEXITY : 

3. TIME COMPLEXITY 3.1. components of time complexity 1. Time complexity of a program depends on: “all the factors that the space complexity depends on” 2. some computer run a program faster & execute 109 instructions/sec, but some computer executes 107 instruction/sec. (e.g.) In program-1, program (c) requires less execution time than the program (a). 3. some compiler take less time than others to generate computer code. 4. smaller problem generally take time than larger problem. 5. Time taken by a program = sum (compiler time & run time (or) execution time)

Slide 16: 

6. Compiled program can run several times without re-compilation. 7. The runtime is denoted as tp (instance characteristic) 8. If we know the characteristic of a compiler we can determine the number of addition, subtraction, multiplication, division , compares, loads, stores etc., Formula for tp: tp (n) = CaADD(n) + CsSUB(n) + CmMUL(n) + CdDIV(n) + …….. Where: n - instance characteristics Ca Cs - time needed for addition, subtraction, division, Cm multiplication Cd ADD,SUB, - functions MUL, DIV

Slide 17: 

9. Two approaches to estimate Run-time of a program are: (a) identify one (or) more key operations and determine number of times the operation performed. (b) determine total number of steps executed by the program. 3.2. operation counts 1. One way to estimate the time complexity of a program (or) method select one (or) more operations – such as “add, multiply, compare”, and determine how many of each is done. 2. The success of this method is depends on: - ability to identify the operations, that contribute to the time complexity. 3. Examples: (a) max element - find out the largest element in an array a[0:n]

Slide 18: 

(b) polynomial Evaluation (c) ranking (d) rank sorting (or) count sorting (e) selection sort (f) bubble sort (e) Selection sort Line-1 Line-2 Line-3 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5

Slide 19: 

Line-4 Line-5 Line-6 => one way to rearrange the elements in an array ‘a’ is a[0] <= a[1] <= ………..<= a[a.length-1] => n = a. length determine the largest elements in ‘n’ & move it to a[n-1]. determine the next largest element in remaining n-1 element & move it to a[n-2]. 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5

Slide 20: 

=> from the example: a[0:5] = [6, 5, 8, 4, 3, 1] is sorted into a[0:5] = [1, 3, 4, 5, 6, 8] => Java coding public static void selectionsort (comparable[] a) { for(int size = a.length; size > 1; size--) { // find max object in a[0:size-1] int j = mymath.max(a,size-1); //move max object to right end mymath.swap (a, j, size-1); } }

3.3. best, worst and average operation counts : 

3.3. best, worst and average operation counts Average case refer to running time of an algorithm as an average taken over all inputs of the same size. Worst case refer to running time of an algorithm as the maximum taken over all inputs of the same size. Best case refer to running time of an algorithm as the minimum taken over all inputs of the same size.

Slide 22: 

Graphical description A B C D E F G input instance Running Time Worst case time best case time 6 5 4 3 2 1 Average case time

Slide 23: 

Examples: (a) sequential search (b) Insertion into a sorted array (c) Rank sort Revisited (d) Selection sort Revisited (e) Bubble sort Revisited (f) Insertion sort (b) Insertion into a sorted Array 1. Insert a new element into a array & the result is a also sorted array. a[0:4] =[2,4,6,8,9] 2. Insert ‘3’ into above array a[0:4] & the result is a[0:5]= a[2,3,4,6,8,9]. 0 1 2 3 4

Slide 24: 

3.The insertion may be done by beginning at the right end & successively moving one position right, to find the location for new element. 4. In our (e.g) we moved 9,8,6& 4 to insert the element 3. Line-1 Line-2 Line-3 Lline-4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 5 5 5 5

Slide 25: 

Line-5 Line-6 5. The best (or) minimum no. of comparison is 1. It happen, when the new element ‘x’ is inserted at right end. 6. The maximum no. of comparison is ‘n’. It happens when ‘x’ is inserted at left end. 7. The average count is 1/n+1 ( ∑ (n-i) + n) = 1/n+1 ( ∑ j + n) 0 1 2 3 4 5 0 1 2 3 4 5 n-1 i=0 j=1 n

Slide 26: 

8. Java coding public static void insert (comparable [ ]a, int n, comparable x) { if( a . length < n + 1) throw new illegalArgumentException (“array not large enough”); //find proper place for x int i; for( i=n-1; i>=0 && x . compareTo a[i]) < 0; i--) a[i+1] = a[i]; a[i+1] = x; // insert x }

Step Count : 

Step Count Methods To Compute The Step Count Introduce variable count into programs Tabular method Determine the total number of steps contributed by each statementstep per execution  frequency add up the contribution of all statements

3.4. step counts : 

3.4. step counts Step count - is a function of the instance characteristics Step - any computation unit that’s independent of the selected characteristics. (e.g) 100 – multiplications may be one step, 10 – additions may be one step but ‘n’ – additions, where : ‘n’ – is an instance characteristics Program Step A program step is a syntactically or semantically meaningful program segment whose execution time is independent of the instance characteristics.

Slide 29: 

Example: abc = a + b + b * c + (a + b - c) / (a + b) + 4 the amount of computing represented by one program step may be different from another program step representation. abc = a + b + c Count - we can determine the no. of steps a program /method takes to complete its task by creating a global variable ‘count’. Count=0 - next introduce statement into the program to increment ‘count’ - each time the statement is executed,’ count’ is incremented. (count++). - the value of the no. of steps taken to terminate the count = program/method

Slide 30: 

Example: (program without ‘count’ variable) public static computable sum (computable [ ] a, int n) { if (a.length == 0) return null; computable sum = (computable) a[0].zero(); for ( int I = 0; I < n; i++) sum.increment (a [i] ); return sum; }

Slide 31: 

Example: (program with ‘count’ variable) public static computable sum (computable [ ] a, int n) { count++; //for conditional and return if (a.length == 0) return null; computable sum = (computable) a[0].zero(); count++; // for preceding statement for ( int I = 0; I < n; i++) { count ++; //for the for statement sum.increment (a [i] ); count++; //for increment } count++; //for last execution of for statement count++; //for return return sum; }

Tabular method description of step count : 

Tabular method description of step count Instead of introducing ‘count’ variable in the statement, build a table to list the total no. of steps that each statement contributes to ‘count’. In the table format first determine the - no. of steps/execution (s/e) of the statement and - next the total no. of times (i.e.frequency) each statement is executed. - next combine above two steps to find out ‘total contribution’ of each statement. - last step is add the contribution of all statements to obtain the step count for entire program. - this overall approaches to obtain a step count is called “ Profiling”.

Matrix Addition : 

Matrix Addition Figure 1.4: Step count table for matrix addition