Empirical Measures
From
(→Empirical counting of operations) |
(→Empirical counting of operations) |
||
| Line 9: | Line 9: | ||
#Identify the appropriate place in your code to increment the counter so that you are counting the behavior that you are interested in | #Identify the appropriate place in your code to increment the counter so that you are counting the behavior that you are interested in | ||
#Output the counter after the task has finished | #Output the counter after the task has finished | ||
| - | + | <br/> | |
As an example, here is a function with 2 very simple nested loops; Analytically, I can see that each loop control is linear with N, but as it is nested, that puts this code into O( N^2 ). Now I want to empirically verify this with a counter, so I create and initialize the counter, increment it in the inner loop, and finally output the value after the loops have completed. | As an example, here is a function with 2 very simple nested loops; Analytically, I can see that each loop control is linear with N, but as it is nested, that puts this code into O( N^2 ). Now I want to empirically verify this with a counter, so I create and initialize the counter, increment it in the inner loop, and finally output the value after the loops have completed. | ||
<br/> | <br/> | ||
| Line 27: | Line 27: | ||
</pre> | </pre> | ||
<br/> | <br/> | ||
| + | It should be noted that adding in additional counters into your code is generally for testing and analysis purposes and should be removed, commented out, or otherwise isolated from final executables provided to users. | ||
==Empirical measurement of time== | ==Empirical measurement of time== | ||
Example using psuedocode to be written | Example using psuedocode to be written | ||
<br/><br/> | <br/><br/> | ||
Revision as of 21:35, 2 April 2009
Empirical analysis of a program is a factual enquiry carried out by recording what is observed or measured from actual run-time behavior of a program. Two of the more common empirical measures of program behavior are actual clock time and operations counting. Measuring clock time usually involves adding calls to the system clock at the begining and end of the process or function that you wish to measure. Measuring operations frequency commonly include counting comparisons, counting assignments (memory writes), and counting the number of times the inner most code in a loop is executed.
Asymptotic measures are "analytical" meaning that we look at the algorithm and deduce it's behavior. Empirical measures are situational observations; we measure real behavior for a specific situation. They are complimentary to each other; empirical measures should validate our analytical view of program behavior.
Empirical counting of operations
Adding automated counting into code is a realatively easy task:
- Create one or more variables to function as counters and initialize them
- Identify the appropriate place in your code to increment the counter so that you are counting the behavior that you are interested in
- Output the counter after the task has finished
As an example, here is a function with 2 very simple nested loops; Analytically, I can see that each loop control is linear with N, but as it is nested, that puts this code into O( N^2 ). Now I want to empirically verify this with a counter, so I create and initialize the counter, increment it in the inner loop, and finally output the value after the loops have completed.
FUNCTION nestedLoops( n )
LET counter1 = 0 //This is the counter to measure execution work
do some initialization work
FOR i FROM 0 TO n BY 1
FOR j FROM y TO 0 BY -1
Let counter1 = counter1 + 1 //Increment the counter
do the functions work
ENDFOR
ENDFOR
output( counter1 ) //Somehow record or output the counter
RETURN work
ENDFUNCTION
It should be noted that adding in additional counters into your code is generally for testing and analysis purposes and should be removed, commented out, or otherwise isolated from final executables provided to users.
Empirical measurement of time
Example using psuedocode to be written
