Empirical Measures

From

← Asymptotic Measures

↑ Contents: CS2

End

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 operations counting and actual clock time. Measuring operation frequency commonly includes counting comparisons, counting assignments (memory writes), or counting the number of times the inner most code in a loop is executed. 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.

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 i 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	

Finally, you would choose a range of values for N to test this code against and observe the recorded values of your counter. The values of the counter should validate the analysis that this function falls in the time complexity class of O( N^2 ).

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 clock time

Similarly, adding automated clock time measurment into code is also relatively easy task:

1. Create one or more variables to store elapsed time
2. Identify the appropriate place in your code to get the system time as the start time (which should be just prior to the code your are interested in measuring)
3. Identify the appropriate place in your code to get the system time as the end time (which should be just after the code your are interested in measuring)
4. Output the difference of the end time from the start time; this is the run time of the code of interest

As an example, here is the same previsou function with 2 very simple nested loops; Analytically, I can see that each loop control is linear with N, but as the loops are nested, this code is in O( N^2 ). Now I want to empirically verify this with clock time:

    FUNCTION nestedLoops( n )    
        do some initialization work

        //Get the starting time from some system call
        LET starttime = systemTime( )  

	FOR i FROM 0 TO n BY 1
            FOR j FROM i TO 0 BY -1
    		do the functions work
            ENDFOR
        ENDFOR

        //Calculate the total time of the critical code
        LET totaltime = systemTime( ) - starttime

        output( totaltime )  //Somehow record or output the time
        RETURN work
    ENDFUNCTION	

Finally, you would choose a range of values for N to test this code against and observe the recorded run times. One issue with clock time is that you will likely have to choose large values of N to get measurable times, or use a very fine scale system clock (in nanoseconds sometimes) if that is available. The comparing the time values over a range of N values should validate the analysis that this function falls in the time complexity class of O( N^2 ).

It should be noted that adding in clock time measures 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.

---

---