Empirical Measures

From

Revision as of 21:26, 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:

1. Create one or more variables to function as counters and initialize them
2. Identify the appropriate place in your code to increment the counter so that you are counting the behavior that you are interested in
3. 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	

Empirical measurement of time

Example using psuedocode to be written