Empirical Measures
From
(→Empirical counting of operations) |
|||
| Line 8: | Line 8: | ||
<br/><br/> | <br/><br/> | ||
==Empirical counting of operations== | ==Empirical counting of operations== | ||
| - | + | Adding automated counting into code is a realatively easy task: | |
| + | #Create one or more variables to fuction 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 | ||
<br/><br/> | <br/><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. | ||
| + | <br/><br/> | ||
| + | <pre> | ||
| + | FUNCTION nestedLoops( N ) | ||
| + | LET counter1 = 0 //This is the counter to measure execution work | ||
| + | do some initialization work | ||
| + | FOR i = 0; i <= y STEP 1) | ||
| + | FOR j = y; j >= 0; j--) | ||
| + | Let counter1 = counter1 + 1 //Increment the counter | ||
| + | do the functions work | ||
| + | ENDFOR | ||
| + | ENDFOR | ||
| + | output( counter1 ) //Somehow record or output the counter | ||
| + | RETURN work | ||
| + | ENDFUNCTION | ||
| + | </pre> | ||
| + | <br/> | ||
Revision as of 21:22, 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 measurement of time
Example using psuedocode to be written
Empirical counting of operations
Adding automated counting into code is a realatively easy task:
- Create one or more variables to fuction 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 = 0; i <= y STEP 1)
FOR j = y; j >= 0; j--)
Let counter1 = counter1 + 1 //Increment the counter
do the functions work
ENDFOR
ENDFOR
output( counter1 ) //Somehow record or output the counter
RETURN work
ENDFUNCTION
