How do we determine how to write a program?
How can we tell if one version of a program is better than another?
As you may have discovered this week, there is more than one way to write a program that will accomplish the same goal. Even the programs that you wrote this week are likely to vary slightly from what your peers wrote!
So, if there's more than one way to write a program, how can you tell which way is better? Most of the time, it comes down to how fast the program runs. Unfortunately, it's not always that simple. The decision often needs to be based on your project goals, which means finding a balance between:
Download the program fibTime.py into your programs directory (don't forget the .py). Go ahead and open the file in gedit. Inside you'll find four different implementations of Fibonacci. Despite being written differently, all four will produce the same result for each input value. You've already see the first two implementations, they're from the Fibonacci loops and recursion modules! The last two have been heavily optimized, don't worry if they don't make sense!
Open a terminal and start IPython. We will be using a new command to time how long it takes each implementation to run called %timeit. This command runs an operation multiple times and displays the best average result.
The result often uses units of time less than one second.
| Unit | Name | Fraction of a Second |
|---|---|---|
| ms | Millisecond | 1 thousandth: 1 / 1,000 |
| μs | Microsecond | 1 millionth: 1 / 1,000,000 |
| ns | Nanosecond | 1 billionth: 1 / 1,000,000,000 |
Do you think recursion or for loops will be faster? Why?
See if you were right by running the following commands in IPython:
from fibTime import *
%timeit fibLoops(32)
%timeit fibRecurse(32)
%timeit superFibLoops(32)
%timeit superFibRecurse(32)
What do you think will happen when we use larger numbers?
Now try using %timeit:
%timeit fibLoops(100000)
%timeit superFibLoops(100000)
%timeit superFibRecurse(100000)
Did the results align with what you expected? Write about it on your webpage!
Finally, try running:
%timeit fibRecurse(500)
You might want to grab a cup of coffee. Better yet, pack your things and prepare for a quick vacation on Pluto, you'll be back before it finishes. In fact, it's going to take over 398,990,454,904,126,259,557,361,443,653,866,998,483,488,600,582,924,986,447, 198,268,510,547,079,964,695,772,354,503,373 YEARS to complete. Stop it with ctrl+c.
When you're done, please answer these questions on your webpage.