It is my first use of classes in Python. I wanted to create something useful and try some new things as I learn this cool language: strategy pattern, testing with nanoseconds precision, curve/poly fitting, and making a graphic presentation. The budget was 150 lines of code: 50 for five Fibonacci number calculations, 50 for testing and checking the results, 50 for presentation. PyCharm was my mentor and strict format enforcer: 22 blank lines. I made it in 149 lines and then added one comment line. Could be a better “curve fit” and “poly fit” string formulas, but it will force me to go over 150 lines.
Here is what this program does:
- Calculates Fibonacci numbers from 2 to 30 by five different methods. Tests if all methods produce the same results and keep the shortest runtime from 10 tries.
- Plots all best times in nanoseconds at four subplots: regular axes, log Y, zoom to 30000 nSec, and zoom+ to 3000 nSec.
- It uses curve_fit from scipy and polyfit from numpy to find the best parameters for math formulas describing the time complexity of these Fibonacci algorithms.
I was happy to see the recursion as (446 * 1.62 ** n) just after the first tests and bug fixing - that is a theoretical O(φ**n) or 1.6180339887…
Critique and suggestion on how to write a better code are welcome.
Should I put all import statement at the top?
Here is the code:
from abc import ABCMeta, abstractmethod
from cachetools import cached, TTLCache
class Fibonacci(metaclass=ABCMeta): # Abstract prototype ######################
def fibonacci(self, n):
if isinstance(n, int) and n >= 0:
return self._fibonacci(n) if n >= 2 else [0, 1][n]
raise ValueError
@abstractmethod
def _fibonacci(self, n):
pass
class FibonacciRecursion(Fibonacci): # 1. Classic and also naive computation ##
def _fibonacci(self, n):
return self.fibonacci(n - 1) + self.fibonacci(n - 2)
class FibonacciCacheTools(Fibonacci): # 2. The cache fixes bad algorithm choice
cache = TTLCache(maxsize=1500, ttl=3600)
@cached(cache)
def _fibonacci(self, n):
return self.fibonacci(n - 1) + self.fibonacci(n - 2)
class FibonacciAddition(Fibonacci): # 3. It is O(n), not O(2**n) as before ####
def _fibonacci(self, n):
f0, f1 = 0, 1
for _ in range(1, n):
f0, f1 = f1, f0 + f1
return f1
class FibonacciAdditionPlus(FibonacciAddition): # 4. Exploiting the test: O(1)
def __init__(self):
self._n = 2
self._f0 = 1
self._f1 = 1
def _fibonacci(self, n):
if n == self._n:
return self._f1
if n < self._n:
self.__init__()
for _ in range(self._n, n):
self._f0, self._f1 = self._f1, self._f0 + self._f1
self._n = n
return self._f1
class FibonacciFormula(Fibonacci): # 5. Formula of Binet, Moivre, and Bernoulli
# Exact integer until Fibonacci(71)
# Float error at Fibonacci(1475) OverflowError: (34, 'Result too large')
S5 = 5.0 ** 0.5 # Square root of 5
def _fibonacci(self, n):
phi = (1.0 + FibonacciFormula.S5) / 2.0 # φ Python speaks greek!
psi = (1.0 - FibonacciFormula.S5) / 2.0 # ψ PyCharm doesn't like it ;-(
return int((phi ** n - psi ** n) / FibonacciFormula.S5)
if __name__ == '__main__': # Testing ... ######################################
import platform
import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import curve_fit
def func1(x, a, b): # function to fit exponential Fibonacci
return '%f * %f**x' % (a, np.exp(b)) if x is None else a*np.exp(b*x)
def func2(x, a, b, c): # function to fit with cubic curve
return '%f + %f*x + %f*x**2' % (a, b, c) if x is None else a+x*(b+c*x)
def first_test(fibonacci_max, repeat): # Collect times, curve fit, and plot
methods = [ # Function to test, color, poly fit, curve fit
[FibonacciRecursion(), 'blue', 2, func1],
[FibonacciCacheTools(), 'orange', 1, func2],
[FibonacciAddition(), 'green', 1, func2],
[FibonacciAdditionPlus(), 'red', 1, func2],
[FibonacciFormula(), 'purple', 1, func2],
]
print('Number,Fibonacci,Times for all methods in nanoseconds')
n_max = fibonacci_max - 1 # we start from n=2 (0, 1 - the same time)
y = [[0 for _ in range(n_max)] for _ in methods]
for j in range(n_max): # Run tests and collect times in array y #######
n = j + 2
old = None
for i, method in enumerate(methods):
best = None
for k in range(repeat):
start = time.perf_counter_ns()
result = method[0].fibonacci(n)
stop = time.perf_counter_ns()
duration = stop - start
if best is None or duration < best:
best = duration
if old is None:
old = result
elif result != old:
print(
'Error: different results %d and %d for function %s'
' F(%d) in call # %d,' %
(old, result, method[0].fibonacci.__name__, n, k+1))
exit(1)
if i == 0:
print(n, ',', old, sep='', end='')
print(',', best, sep='', end='')
y[i][j] = best
print()
plt.figure(1) # Start plotting ########################################
plt.suptitle('Time(n) Complexity of Fibonacci Algorithms. n = 2,3,...,'
'%d,%d' % (n_max, fibonacci_max))
x = np.array([i + 2 for i in range(n_max)])
plt.subplots_adjust(hspace=0.3)
for i in range(4):
plt.subplot(221 + i)
for j, m in enumerate(methods):
s = str(m[0].__class__.__name__)[len('Fibonacci'):]
plt.plot(x, y[j], 'tab:' + m[1], label=s)
plt.title(['time in nanoseconds', 'log(Time)', 'zoom', 'zoom+'][i])
plt.grid(True)
if i == 0:
plt.legend()
elif i == 1:
plt.semilogy()
else:
x_min, x_max, _, _ = plt.axis()
plt.axis([x_min, x_max, 0.0, 30000.0 if i == 2 else 3000.0])
for i, m in enumerate(methods): # Curve and poly fitting ##############
plt.figure(2 + i)
name = str(m[0].__class__.__name__)[len('Fibonacci'):]
plt.plot(x, y[i], 'ko', label=name)
c, _ = curve_fit(m[3], x, y[i])
c_name = 'curve fit:' + m[3](None, *c)
plt.plot(x, m[3](x, *c), 'y-', label=c_name)
p = np.poly1d(np.polyfit(x, y[i], m[2]))
p_name = 'poly fit: ' + str(p)
plt.plot(x, p(x), m[1], label=p_name)
plt.legend()
print('%s\n%s\n%s\n' % (name, c_name, p_name))
plt.show()
print('Python version :', platform.python_version())
print(' build :', platform.python_build())
print(' compiler :\n', platform.python_compiler())
first_test(fibonacci_max=30, repeat=10)
The output:
$ python fibonacci.py
Python version : 3.7.3
build : ('v3.7.3:ef4ec6ed12', 'Mar 25 2019 16:52:21')
compiler :
Clang 6.0 (clang-600.0.57)
Number,Fibonacci,Times for all methods in nanoseconds
2,1,1027,2598,731,526,874
3,2,1638,2516,769,523,956
4,3,2818,2470,806,532,904
5,5,4592,2413,840,526,902
6,8,7571,2531,936,562,955
7,13,12376,2490,909,538,999
8,21,20528,2588,972,551,973
9,34,33349,2628,1074,581,1037
10,55,60107,2782,1116,581,997
11,89,85465,2421,1056,534,939
12,144,137395,2429,1101,534,942
13,233,222623,2411,1136,539,955
14,377,360054,2476,1216,551,938
15,610,600066,2736,1332,563,1006
16,987,971239,2529,1323,541,937
17,1597,1575092,2479,1359,552,937
18,2584,2565900,2632,1464,563,962
19,4181,4071666,2583,1485,555,953
20,6765,6630634,2503,1481,532,914
21,10946,10843455,2527,1571,522,930
22,17711,18277770,2617,1646,548,952
23,28657,28838223,2620,1739,573,967
24,46368,47167582,2481,1713,543,932
25,75025,77326177,2481,1709,531,909
26,121393,126154837,2587,1799,546,944
27,196418,205083621,2527,1857,548,942
28,317811,329818895,2444,1822,531,952
29,514229,533409650,2493,1932,551,946
30,832040,866064386,2509,1967,553,947
Recursion
curve fit:448.753271 * 1.619991**x
poly fit: 2
1.751e+06 x - 4.225e+07 x + 1.829e+08
CacheTools
curve fit:2492.458456 + 7.778994*x + -0.252776*x**2
poly fit:
-0.3099 x + 2539
Addition
curve fit:636.162562 + 42.475661*x + 0.074421*x**2
poly fit:
44.86 x + 622.3
AdditionPlus
curve fit:528.372414 + 2.642894*x + -0.076063*x**2
poly fit:
0.2089 x + 542.5
Formula
curve fit:920.230213 + 5.076194*x + -0.163003*x**2
poly fit:
-0.1399 x + 950.5
Graphics: 
