# 1 1 2 3 5 8 13 21 39 ...

# codez la fonction FiboRec (avec une fonction récursive)
def FiboRec(n) :
    if n <=2 : return 1
    return FiboRec(n-1)+FiboRec(n-2)

for i in range(1,40) : print(i,FiboRec(i))

"""
Explanation: <font color="red" size="6"><b>Programmation dynamique</b></font>
<font color="blue" size="5"><b>I Fibonacci récursif naïf</b></font>
End of explanation
"""


from timeit import timeit
import matplotlib.pyplot as plt


abcisse = [5,10,15,20,25,28,30]
ordonnee=[0 for _ in range(len(abcisse))]
for i in range(len(abcisse)) :
    ordonnee[i] = timeit("FiboRec(abcisse[i])", number=10, globals=globals())

# Graphique pour le tri sélection en rouge
plt.plot(abcisse, ordonnee, "ro-") # en rouge


plt.show()
plt.close()

"""
Explanation: Que constatez vous ???
End of explanation
"""


# Codez la version avec mémoïsation

def Fibo(n,memo) :
    if n in memo.keys() : return memo[n]
    #if n<=2 : return 1
    memo[n] = Fibo(n-1,memo)+Fibo(n-2,memo)
    #memo[n]=1+1
    return memo[n]
def Fibomem(n):
    memo={1:1,2:1}
    return Fibo(n,memo)

for i in range(1,40) : print(i,Fibo(i,{1:1,2:1}))

"""
Explanation: hmmm.... pas fameux !!!
Mais il fallait s'y attendre, la complexité est exponentielle.
<font color="blue" size="5"><b>II Fibonacci récursif + mémoïsation</b></font>
End of explanation
"""


from timeit import timeit
import matplotlib.pyplot as plt
import sys

sys.setrecursionlimit(90000)

abcisse = [i for i in range(1000,22000,3000)]
ordonnee=[0 for _ in range(len(abcisse))]
for i in range(len(abcisse)) :
    ordonnee[i] = timeit(stmt="Fibomem(abcisse[i])", number=100, globals=globals())

# Graphique 
plt.plot(abcisse, ordonnee, "ro-") # en rouge


plt.show()
plt.close()

# Variante :

def Fibomem2(n,memo=None) :
    if memo == None : memo={1:1,2:1}
    if n in memo.keys() : return memo[n]
    memo[n] = Fibomem2(n-1,memo)+Fibomem2(n-2,memo)
    return memo[n]
Fibomem2(100)

from timeit import timeit
import matplotlib.pyplot as plt
import sys

sys.setrecursionlimit(90000)

abcisse2 = [i for i in range(1000,15000,3000)]
ordonnee2=[0 for _ in range(len(abcisse2))]
for i in range(len(abcisse2)) :
    ordonnee2[i] = timeit(stmt="Fibomem2(abcisse2[i])", number=100, globals=globals())

# Graphique 
plt.plot(abcisse, ordonnee, "ro-") # en rouge
plt.plot(abcisse2, ordonnee2, "go-") # en vert


plt.show()
plt.close()

"""
Explanation: D'emblée... c'est mieux non ?
Voyons le graphique :
End of explanation
"""


%%time

def fibo1(n: int) -> int:
    fi, fip1 = 0, 1
    for i in range(n):
        fi, fip1 = fip1, fi + fip1
    return fi

for n in range(100, 110):
    print(f"fibo1({n}) = {fibo1(n)}")

for n in [10, 100, 1000, 10000]:
    print(f"Pour n = {n}, fibo1 a pris ce temps : ", end='', flush=True)
    %timeit fibo1(n)

"""
Explanation: Et avec une boucle for sans mémoire ?
End of explanation
"""


%%time

def fibo2(n: int) -> int:
    fi  : int = 0
    fip1: int = 1
    fip2: int = 2
    i   : int = 1
    while i <= n:
        fip2 = fi + fip2
        i += 1
        fi = fip1
        fip1 = fip2
    return fi

for n in range(100, 110):
    print(f"fibo2({n}) = {fibo2(n)}")

for n in [10, 100, 1000, 10000]:
    print(f"Pour n = {n}, fibo2 a pris ce temps :", end='', flush=True)
    %timeit fibo2(n)

"""
Explanation: Et avec une simple boucle while, sans for ?
End of explanation
"""


%load_ext cython

%%cython

def fibo3(unsigned long long n):
    cdef unsigned long long fi = 0
    cdef unsigned long long fip1 = 1
    cdef unsigned long long fip2 = 2
    cdef unsigned long long i = 1
    while i <= n:
        fip2 = fi + fip2
        i += 1
        fi = fip1
        fip1 = fip2
    return fi

%%time
for n in range(100, 110):
    print(f"fibo3({n}) = {fibo3(n)}")

for n in [10, 100, 1000, 10000]:
    print(f"Pour n = {n}, fibo3 a pris ce temps :", end='', flush=True)
    %timeit fibo3(n)

"""
Explanation: Et avec une fonction Cython ?
On va tester de compiler la fonction en C avec Cython pour voir si on obtient des performances "vraiment linéaires" :
End of explanation
"""


globals().update({'ok': 'ok'})

from timeit import timeit
import numpy as np
import matplotlib.pyplot as plt
import sys

sys.setrecursionlimit(90000)

exp_min, exp_max, nb_tailles = 1, 4, 10
number_timeit = 1000

tailles = np.array(np.ceil(np.logspace(exp_min, exp_max, nb_tailles)), dtype=int)
print(f"Tailles = {tailles}")

fonctions = {
    "Linéaire (for)": fibo1,
    "Linéaire (while)": fibo2,
    "Linéaire (Cython)": fibo3,
}
temps = {}

for nom, fonction in fonctions.items():
    temps[nom] = np.zeros_like(tailles)
    print(f"Estimation des temps pour {nom} ({fonction})...")
    for i, taille in enumerate(tailles):
        temps[nom][i] = timeit(stmt="fonctions[nom](taille)",
                               number=number_timeit,
                               globals={'fonction': fonction, 'taille': taille, 'fonctions': fonctions, 'nom': nom}
                               )
        #print(f"Calling %timeit {fonction}({taille}): ")
        #%timeit fonction(taille)

# Graphique
plt.figure(figsize=(12, 8), dpi=300)
plt.title("Comparaison de trois fonctions calculant Fibo(n) en complexité linéaire ?")

markers = ['+', 'o', 'd']
for i, (nom, fonction) in enumerate(fonctions.items()):
    plt.plot(tailles, temps[nom], label=nom, marker=markers[i % len(fonctions)])

plt.legend()
plt.show()


"""
Explanation: Bien sûr, on peut encore écrire du code Cython plus efficace, cf la doc.
Et avec Cython on utilise les types C  donc les entiers bornés, d'où mon utilisation de unsigned long long, le type natif d'entirs C le plus grand possible.
-- Partie rédigée par Lilian Besson (@Naereen)
Graphiques avec plein de comparaison
End of explanation
"""


# Approche de bas en haut


def FiboMonte(n) :
    fib=[0 for _ in range(n+1)]
    fib[1]=fib[2]=1
    for i in range(3,n+1) :
        fib[i] =fib[i-1]+fib[i-2]

    return fib[n]

from timeit import timeit
import matplotlib.pyplot as plt
abcisse = [i for i in range(1000,22000,3000)]
ordonneeMonte=[0 for _ in range(len(abcisse))]

ordonneeMonte=[0 for _ in range(len(abcisse))]
for i in range(len(abcisse)) :
    ordonneeMonte[i] = timeit(stmt="FiboMonte(abcisse[i])", number=50, globals=globals())

# Graphique 
plt.plot(abcisse, ordonnee, "ro-") # en rouge
plt.plot(abcisse, ordonneeMonte, "go-") # en vert


plt.show()
plt.close()

"""
Explanation: <font color="blue" size="5"><b>III Fibonacci : approche de bas en haut</b></font>
End of explanation
"""


