4
\$\begingroup\$

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:

  1. 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.
  2. Plots all best times in nanoseconds at four subplots: regular axes, log Y, zoom to 30000 nSec, and zoom+ to 3000 nSec.
  3. 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: enter image description here

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Well done on presenting intent and constraints upfront. One thing nagging me: why not choose an argument range to try and push the limits of integer representations (somehow managing run time of the plain recursive approach (and checking for deviation of "the formula result")). \$\endgroup\$ – greybeard Apr 2 at 5:58
  • \$\begingroup\$ Thank you for the welcome and the comment. Actually, I did comment the line with "[FibonacciRecursion(), 'blue', 2, func1]," and "elif result != old:" in order to push the limit and see what will happen next: they stay steady flat O(1) except Addition O(n). Also started to write another test program to see the error in "the formula result" and a possibility to compensate it: the absolute error starts almost as another Fibonacci from 72 with F(n-71) range, but the relative error has a linear grow from 2.0e-15 at F(72) to 4.4e-14 at F(1314). \$\endgroup\$ – Alex Lopatin Apr 2 at 8:51
-1
\$\begingroup\$

I'm not really sure why you used classes for your Fibonacci functions. In python it is generally better style to just use a function.

\$\endgroup\$
  • \$\begingroup\$ I started with functions but soon realized that they will benefit from common class if I want to maintain, share this project, and others contribute to it. I had the questions: How I can enforce all functions have the same interface? Some of the function can benefit from initialization and storing the temporary variables between calls. How this can be done uniformly? How I just write a code to check the argument once and reuse for all? How do I compare the performance of the same function with different parameters (cache size)? The classes had all the answers to these my questions. \$\endgroup\$ – Alex Lopatin Apr 2 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.