| home page - news - syllabus - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
| Self-Study 1 - Self-Study 2 - Self-Study 3 - Self-Study 4 - Self-Study 5 - Self-Study 6 - Self-Study 7 |
| Measuring the Running Times of Algorithms |
Lectures in this course will generally focus on the “asymptotic analysis” of the running times of algorithms.While this is useful for the selection of algorithms when inputs can be arbitrarily large it is not sufficient during software development when resource requirements are not restrictive and optimization of software may be required.
In this exercise we will step through the process of using a profiler to learn more about how software actually works in practice. An advantage of this approach is that is guaranteed to take into account influences like the use of a memory hierarchy that will affect the performance of an algorithm every time it is run. A disadvantage is that it is also effected by influences like system load at the time the program is run — things that are unpredictable, not under our control, and likely to change from execution to execution.
So — as was the case for the use of proofs of correctness and testing, — asymptotic analysis and the profiling of software are both important activities that tend to complement each other. Both an asymptotic analysis and the use of a profiler can help to provide information about the resources that your program uses.
Previous self-study exercises have introduced several algorithms that can be used to compute the nth Fibonaaci number, Fn for a given nonnegative integer n.
While it is certainly not clear from its recursive definition it is possible to show that Fn is the integer that is closest in value to
φn / √ 5
where φ is the “golden ratio”
φ = (1 + √5)/2 ≈ 1.618
The first algorithm that we considered was a simple recursive algorithm that implemented the recursive definition for the Fibonacci numbers directly; one of the example problems in the lecture notes on the analysis of algorithms asks you to show that the number of steps used by this algorithm is less than or equal to 6 Fn+1− 4 for every integer n ≥ 0. A very similar argument (by induction on n) can be used to prove that this running time is also greater than or equal to 2 Fn+1 for every nonnegative integer n as well.
Using all of the above one can show that there exists a pair of positive constants cL and cU such that, for all sufficiently large n (that is, for all n ≥ N0 for some nonnegative constant N0) it is true that
cL φn ≤ T(n) ≤ CU φn
where T(n) is the number of steps used by this algorithm on input n. In other words (using asymptotic notation introduced at the beginning of the third week of classes),
T(n) ∈ Θ(φn).
The above inequalities imply that, for sufficiently large n, the ratio T(n)/φn is bounded from below by the positive constant cL and bounded from above by the positive constant cU.
It is reasonable, under these circumstances, to ask the following.
Question 1: Does the ratio T(n)/φn converge to some value as n approaches infinity? If it does, then what value does it converge to?
A related question that would likely be of interest is:
Question 2: Does the ratio, of the running time (in milliseconds) used by this method on input n, to φn, converge?
A significant problem with the above question is that the “running time on input n” is not well-defined! If you run the program numerous times using the same input then you should expect the program to have a (slightly) different running time each time it is executed. Furthermore, we can expect these running times to be very different if you are running the same program with the same input on different computers or under significantly different environmental conditions.
Nevertheless it is interesting to look for evidence that the ratio of a “typical” running time (or the average of the running times for several trials) to φn converges. If we find evidence that it does converge then this might be viewed as evidence that the ratio T(n)/φn converges too.
In the previous self-study exercise, we discovered that the method SFibonnaci.fib (included as part of the Fibonacci1 package) could only be used by other methods in the same package.
Modify the source code for this method to eliminate this restriction (you will need to change exactly one word in order to do this) and then recompile.
Download, examine, and compile the program Fib35.java. This evaluates the 35th Fibonacci number without displaying it.
Note that if you solved the first problem then you should be able to compile and run this program with no problems.
Modify this program in order to produce programs Fib36.java, Fib37.java, Fib38.java, Fib39.java and Fib40.java, which should be virtually identical to Fib36.java — including only those changes needed to ensure that each can be used to compute one of the next five Fibonacci numbers after F35 (and is documented appropriately).
If you have not already done so, read the information about Jrat that has been provided for CPSC 331 students. Make sure that you are able to use this software to store information about the time used when software is executed, and to view the information that has been stored.
Note: This next step may require the use of a computer for several hours. You don’t actually need to do much — there are only thirty commands to be executed here if you do exactly what I did, and, of course, you can type in a single statement causing several of these to be executed, one after the other!
However, it will take the computer a while to carry out your instructions! For example, on my workstation at school, the initial commands each required approximately thirty seconds, and the final ones each needed about five minutes. The computer you are using might, possibly, be slower than mine!
That said: Please run each of the programs Fib35.java, Fib36.java, ..., Fib40.java several times using the profiler. Again, I did this with each program five times, and this took several hours using the reasonably fast computer in my office.
A spreadsheet containing some of the timing information I obtained is now available.
If you have got this far you will have seen that quite a bit of data is provided when you use JRat. The timing information I included was provided for “Method Time” for the SFibonacci class, found on JRat’s “Hierarchy“ tab.
Replace the timing information I obtained with the timing information you have discovered. Have the expected times needed to compute the 50th, 60th and 70th Fibonacci numbers changed significantly?
Consider again the relationship between Fn and φn given above. It should be reasonably clear that the ratio of running time on input n to φn convergest to some value if and only if the ratio of running time on input n to Fn also converges — to some other related value.
If the timing data you have obtained is similar to mine then you are likely seeing some evidence that these ratios do converge.
That’s interesting — but you might have noticed something when you began to use JRat: The execution of code got slower!
The Unix command time can be used to obtain timing information for any statement that can be executed from the command line.
For example, when I execute the command
time java Fib35
I see something like the following displayed — virtually instantaneously — as output:
Computing the 35th Fibonacci Number...
0.18user 0.01system 0:00.22elapsed 88%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (1major+3118minor)pagefaults 0swaps
It is possible that you will see something like the following instead:
Computing the 35th Fibonacci Number...
0.184u 0.011s 0:00.27 70.3% 0+0k 0+0io 1pf+0w
If that is true then you can see something looking more like the first sample output by executing the command, instead of the one given above:
/usr/bin/time java Fib35
Apply the time command to your own routines.
The most interesting values generated by this utility, for our purposes, are the ones in the middle — a time (in hours, minutes, and seconds) and a percentage. The time is the elapsed time for the computation that was carried out — indicating, above, that this execution of Fib35 required 0.27 seconds — while the percentage tells me something about the extent to which my computer’s CPU was occupied during this computation.
In contrast, the average running time reported for Fib35 when the profiler is used is slightly more than 32 seconds — execution appears to be a little over 100 times slower, when the profiler is used.
One might therefore wonder you would bother with a profiler!
The value of a profiler becomes somewhat more obvious if you implement and obtain timing data for a program that includes several nontrivial methods. After exploring a bit in the “JRat Desktop,” you should discover that you can find information about the time was spent for execution of each one of these methods. This can be particularly helpful if it shows that one (or a small number) of these methods are more heavily used than the others: It would follow that improvements in the performance of the more heavily used methods would be expected to have more of an impact on the overall performance of this program than improvements in the performance of the other methods.
Optimization takes time and effort — and, as mentioned in class, optimization tends to make code somewhat less readable and somewhat harder to maintain! Optimization should therefore be done selectively — and it can be very useful to have to have a tool, like a profiler, in order to decide where you need to optimize your code (when you have determined that you need to).
Returning to our Fibonacci number exmaple — if you use time to measure the runnning times needed to compute F35,..., F40, you might not think that our simple recursive method is so bad, after all.
Modify one of these programs once again, to produce a sequence of similar programs that can be used to evaluate F41, F42,..., F45 and F50.
Then use time to get information about the running times needed for these computations.
If the data you have obtained resembles the data I did then you have likely discovered the following.
Once again, it appears that the ratio of running time (for input n) to φn is converging to a positive constant.
This is not a very efficient algorithm. Based on the information I obtained I would estimate that — in the unlikely event that these computations are actually allowed to run to completion — the evaluation of F60 would requre approximately five hours, the evaluation of F70 would require most of a month, and the evaluation of F80 would require most of a decade.
If you are interested in learning more about recursive algorithms and their efficiency, then the following exercise might be of interest: Modify the slow recursive algorithm so that it initializes an array, of length 11, to include the Fibonacci numbers F0, F1,..., F10. If the input is one of the integers between 0 and 10 then the algoorithm should simply access this array to obtain and return its output; otherwise it should call itself recursively, in the usual way.
If you implement this is a method and obtain timing information for the computation of the Fibonacci numbers that have been used above then you will probably be somewhat encouraged once again.
However, you will be disappointed (once again) if you use your algorithm to compute F51, F52, F53, F54 and F55, and then estimate the times needed by it to compute F60, F70, F80, and F90.
One can use mathematical induction to prove that the running time of this algorithm on input n is (still) in Θ(φn).
On the other hand, several very different algorithms for the computation of Fibonacci numbers were also introduced as part of Self-Study Exercise #2. You may recall that one of them could be used to compute F100 very quickly. Indeed, the techniques for the analysis of the worst case running times of algorithms presented in class can be used to establish that this algorithm can be used to evalute F200, F300 and even F500 very, very quickly, as well.
I hope that this exercise has been of interest — and that it gives you an idea of why profilers (and other Unix tools that can be used to time the execution of programs) are useful.
On the other hand, you should also have a better understanding of the following: Optimization near the end of software development cannot replace the intelligent choice of an efficient algorithm near the beginning of development, during the design stage.
Quite a bit of the rest of this course will help you to learn more about the efficient algorithms that you should be choosing, when you need to solve problems that are large.
|
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F10/tutorials/self-study5.html |