Timing Code

and Revisiting Fibonacci Festival from 2006

I originally wrote about Fibonacci numbers in 2006. Today, along with Sarah Wait Zaranek, we'd like to discuss some of those same ideas, but focus only on execution time. In R2013b, MATLAB includes a new timing function, timeit, one that I mentioned in some earlier posts when it was only available on the MATLAB File Exchange.

Contents

Using timeit

To use timeit, you simply pass in a function handle that requires no inputs. If your function requires input values, you can pass them in by creating an anonymous function, where the values are captured from the current workspace. You can learn more about function handles in the MATLAB documentation, and find examples and discussions on this blog.

timeit runs the code several times to ensure that any first-run timing effects do not affect the results - and returns the median time. If you wish to time your function in the situation where it returns more than 0 or 1 output values, you can specify that as one of the inputs to timeit.

Four Algorithms

In the earlier Fibonacci post, I introduce and times four algorithms. Today we will use the same algorithms, coded as separate programs, in conjunction with timeit. Since we have four algorithms, we will initialize a vector for collecting the timing information.

fibTimes = zeros(1,4);

Straightforward for-loop

Let's calculate 102 Fibonacci values (since the first 2 are known already, [1, 1]).

nf = 102;
type fibloop

function fibs = fibloop(nf)
fibs(1) = 1;
fibs(2) = 1;
for n = 3:nf
    fibs(n) = fibs(n-1)+fibs(n-2);
end

To use timeit, we simply give it a function handle to the function we wish to time.

fibTimes(1) = timeit(@()fibloop(nf));

for-loop with Preallocation

You've all heard it before. One reason the former calculation took so much time is at least alleged to be because of growing the array fibf each time through the loop. So now let's use the same loop, but preallocate the output array so it doesn't need to grow during the calculation.

type fibloopPrealloc

function fibs = fibloopPrealloc(nf)
fibs = ones(1,nf);
for n = 3:nf
    fibs(n) = fibs(n-1) + fibs(n-2);
end

Now time it.

fibTimes(2) = timeit(@()fibloopPrealloc(nf));

Recursive Function

We can use recursion to calculate successive terms, as I showed in that earlier post. Here's the code.

type fibRecursive

function fibs = fibRecursive(n)
if n == 1,
    fibs = 1;   % First element is 1.
    return;
elseif n == 2
    fibs = [1 1];  % First two elements are 1.
else
    % Call fibrec with previous result and compute next one from it.
    fm1 = fibRecursive(n-1); 
    fibs = [fm1 fm1(end)+fm1(end-1)];
end

And now let's use it to calculate the first chunk of Fibonacci numbers.

fibTimes(3) = timeit(@()fibRecursive(nf));

Use filter to Calculate the Sequence

I also explained in the earlier Fibonacci post how to use filter to calculate the sequence as well. Here's the code.

type fibFilter
fibTimes(4) = timeit(@()fibFilter(nf));

function fibf = fibFilter(n)
x = [1 zeros(1,n-1)];
a = [1 -1 -1];
b = 1;
fibf = filter(b, a, x);

Compare Computation Times

It's time to see how quickly the various methods performed. We have multiplied the times by 1000 to make reading the numbers easier.

fprintf('%s\n\n','Compare Times (in milliseconds)')
meths = ['loop           ',...
         'prealloc       ',...
         'recursive      ',...
         'filter         '];
fprintf('%s\n\n',meths)
fprintf('%2.9f    ', fibTimes*1000), fprintf('\n')

Compare Times (in milliseconds)

loop           prealloc       recursive      filter         

0.040766819    0.010003257    0.517234655    0.010549081    

Do You Do Lots of Timing?

Do you do lots of timing? How do you do it? Profiler? Will timeit help? Let us know here.

Get the MATLAB code

Published with MATLAB® R2013b

Published with MATLAB® R2013b