Sometimes you might find yourself wanting or needing to know just how fast (or slow) a particular piece of code is. You might be looking to make as many micro-optimisations as possible, have the most efficient code, or you are just curious about whether
The majority of, if not all, programming languages provide some form of time utilities and we can use those utilities to measure how long a particular piece of code takes to execute. Of course, this can vary greatly from machine to machine and even from one execution to the next. Because of these variations, the exact numbers provided by measuring code aren’t necessarily useful, but looking at the differences between the execution of different functions that do the same thing, in a different way, is.
For example, in Java, the
We’ll use Java’s
The Formula
To time a piece of code, we simply record the time before executing the code, and then record it again after. The difference between those two timestamps is the duration the code took to execute:
startTime = System.currentTimeMillis();
// ... some code to time
endTime = System.currentTimeMillis();
duration = endTime - startTime;
Fibonacci
Here’s a method for calculating the nth Fibonacci number, written in Java.
static int fibN(int n) {
if (n <= 1) {
return n;
} else {
return fibN(n - 1) + fibN(n - 2);
}
}
This method is great for demonstrating recursion but it's terribly inefficient for the task at hand. A more efficient method of computing the nth Fibonacci sequence would be to literally count from the first to the nth sequence number. To demonstrate this, I'll be timing the code execution of both the method above, fibN(), and the method below, fibN2().
static int fibN2(int n) {
int current = 1;
int previous = 0;
int next = 1;
int temp = 0;
for (int i = 1; i < n; i++) {
temp = current;
next = previous + current;
current = next;
previous = temp;
}
return next;
}
Each method will be called from within a loop 40 times, the nanoTime() being noted before the loop starts and when the loop ends in order to calculate execution time. Remember, end time minus start time equals duration. So, here's the full class for this process:
class Fib {
static long startTime = 0;
static long endTime = 0;
static long duration = 0;
static long duration2 = 0;
static final int n = 40;
public static void main(String[] args) {
System.out.println("");
startTime = System.nanoTime();
int a = 0, b =0;
for (int i = 1; i <= n; i++)
a = fibN(i);
endTime = System.nanoTime();
duration = (endTime - startTime);
double ms = ((double)duration/1000000.d);
System.out.println("execution took " + duration + " nanoseconds (" + ms + "ms), recursive");
startTime = System.nanoTime();
for (int i = 1; i <= n; i++)
b = fibN2(i);
endTime = System.nanoTime();
duration2 = (endTime - startTime);
ms = ((double) duration2/1000000.d);
System.out.println("execution took " + duration2 + " nanoseconds (" + ms + "ms), non-recursive");
System.out.println("Fibonacci number " + n + ": " + a);
System.out.println("Fibonacci number " + n + ": " + b);
}
static int fibN(int n) {
if (n <= 1) {
return n;
} else {
return fibN(n - 1) + fibN(n - 2);
}
}
static int fibN2(int n) {
int current = 1;
int previous = 0;
int next = 1;
int temp = 0;
for (int i = 1; i < n; i++) {
temp = current;
next = previous + current;
current = next;
previous = temp;
}
return next;
}
}
You'll notice that there is no data output within the timed code, this is because printing information out to the user can drastically increase the time it takes for our code to execute, its a little bit computationally expensive.
The output of executing the above class is:
execution took 723062375 nanoseconds (723.062375ms), recursive
execution took 9875 nanoseconds (0.009875ms), non-recursive
Fibonacci number 40: 102334155
Fibonacci number 40: 102334155
As you can see, the non-recursive function - fibN2() - is considerably faster than fibN(). Again, we don't care about the exact numbers we get, just the difference. So from this we can see that simply adding all the numbers between 1 and
A final note, nanoseconds are pretty small, a million times smaller than a millisecond. We can change
