fibonacci.py

# /usr/bin/python3
"""Profile Fibonacci sequence computation"""
from typing import List

from profiler import export_profiling_events
from profiler import profile


@profile
def fibonacci_recursive(n: int):
    if n <= 1:
        return n
    return fibonacci_recursive(n-2) + fibonacci_recursive(n-1)


@profile
def fibonacci_top_down(n: int):
    @profile
    def _fib_top_down(n: int, dp: List[int]):
        if dp[n] >= 0:
            return dp[n]
        dp[n] = _fib_top_down(n-2, dp) + _fib_top_down(n-1, dp)
        return dp[n]
        
    dp = [-1]*(n+1)
    dp[0] = 0
    dp[1] = 1
    return _fib_top_down(n, dp)


@profile
def fibonnaci_bottom_up(n: int):
    f0, f1 = 0, 1
    for _ in range(n-1):
        f0, f1 = f1, f0+f1


if __name__ == "__main__":
    n = 10
    fibonacci_recursive(n)
    fibonacci_top_down(n)
    fibonnaci_bottom_up(n)
    export_profiling_events("./profiling.json")