This post compares a few implementations of calculating the first 10,000 numbers in the Fibbonacci sequence.
The Fibbonacci sequence is defined such that the next number in the sequence is the sum of the previous two:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
This is some prep work I did to test numba on the HPC cluster at Sheffield University. I am hoping to get more fancy stuff running using numba on the cluster.
First off we start with a nice simple and short Python implementation:
def fib(n): fib = [0, 1] while len(fib) < n+1: fib.append(fib[-2] + fib[-1]) return fib[1:]
This implementation creates a list with the first two elements in (some consider the first 0 as part of the sequence) and then loops until the length of the output list is the correct length (+1 because of the 0) adding the next element in as the sum of the previous two.
100 loops, best of 3: 7.39 ms per loop
This implementation is respectable, but not exactly fast.
Next up we are going to use a little bit of more modern Python magic to see if we can make a pure Python implementation. This uses an interator which stores it's state when 'yield' is called, upon the next time the iterator is called it will resume from where it left off.
def fib_generator(n): previous, current = 0, 1 yield current i = 1 while i < n: previous, current = current, previous + current yield current i += 1
100 loops, best of 3: 5.88 ms per loop
This is a litte quicker, which is nice.
Next up we are going to try and use numpy. In this example we define an array the length of the desired sequence and then fill it up in a for loop:
import numpy as np
def fib_numpy(n): fib = np.zeros(n) fib = 1 for i in range(2, n): fib[i] = fib[i-2] + fib[i-1] return fib[1:]
100 loops, best of 3: 5.86 ms per loop
/home/cs1sjm/.conda/envs/numba/lib/python3.4/site-packages/ipykernel/__main__.py:5: RuntimeWarning: overflow encountered in double_scalars
This does not give us much, if anything over the generator example.
Now we are going to use numba which is a just in time compilation library for Python, which makes things SUPER speedy!
from numba import jit
@jit def loop(fib): for i in range(len(fib)): fib[i] = fib[i-2] + fib[i-1] return fib def fib_numba(n): fib = np.zeros(n) fib = loop(fib) return fib
The slowest run took 2075.80 times longer than the fastest. This could mean that an intermediate result is being cached 10000 loops, best of 3: 45 µs per loop
This makes a MASSIVE difference! In fact probably too much of a difference, something fishy is probably going on here.
Finally we shall use the Cython package for completeness:
%%cython import numpy as np cimport numpy as np def fib_cython(int n): cdef np.ndarray fib = np.zeros(n) cdef int i fib = 1 for i in range(2, n): fib[i] = fib[i-2] + fib[i-1] return fib[1:]
100 loops, best of 3: 2.28 ms per loop
/home/cs1sjm/.conda/envs/numba/lib/python3.4/site-packages/ipykernel/__main__.py:257: RuntimeWarning: overflow encountered in double_scalars
This isn't a bad speed up and there are more optimisations you can do with cython.