Bonjour, j'ai un petit souci en programmant un algo visant à comparer les vitesses d’exécutions de deux programme calculant les termes de la suite de Fibonacci, l'un en récursif et l'autre en itératif. Je mets le code en image.

Ce code est censé m'afficher cela :

Mais au lieu de ça, il me renvoie cela :

Si quelqu'un pouvait me dire où sont mes erreurs ou comment re écrire ce code ce serait génial.
En vous remerciant par avance.
Cordialement.

Sans le code, à part te dire qu'il y a un os dans le pâté....

On voit rien sur ton image. Mets ton code dans la balise code <>.

Bon il y a un problème avec ta variable t.

Tu fais un t = time() et ensuite t -= t ce qui fait toujours 0.
Il faut que tu fasses start = time() au début.

Ensuite, tu exécutes ta fonction.

Et ensuite end = time() - start pour mesurer le temps écoulé entre le début (start) et la fin (time()).

Et ensuite tu ajoutes end dans it ou rec :

rec.append(end)

Excusez-moi je ne savais pas qu'il y avait une balise code, je suis nouveau.

Du coup Azerban, j'ai bien compris ce que tu m'as dit et j'ai modifié le code comme ceci :
from __future__ import unicode_literals from time import time rep=10 it=[] for k in range(rep): start=time() Fibo(k) #Calculs des premiers termes de la suite# end=time()-start it.append(end) #Stockage des temps de calculs# rec=[] for i in range(rep): start=time() Fibo_rec(i) end=time()-start rec.append(end) import matplotlib.pyplot as plt ab=range(rep) plt.plot(ab, rec, color="b", label="Version recursive") plt.plot(ab, it, color="r", label="Version iterative") plt.legend(loc=2) #Affichage de la légende en haut à gauche# plt.show()

Et cela me renvoie toujours une courbe constante comme dans la troisième image de mon premier message.

Ah mais en mettant le start à l'extérieur de la boucle ça serait mieux
Et ça me donne ça :

Il y a toujours un problème mais je ne vois pas lequel... Car la courbe itérative reste constante à 0 donc cela veut dire qu'aucune valeur différente de 0 n'est ajoutée à la liste "it" et la courbe récursive ne bouge qu'à n=8...

Poste correctement l'intégralité de ton code dans la balise code.

Voilà :

from __future__ import unicode_literals
from time import time

def Fibo(n):
    if n==0:
        return(0) #Cas U0
    elif n==1:
        return(1) #Cas U1
    else:
        F_2=0
        F_1=1
        som=0
        for i in range(2, n+1):
            som=F_1+F_2 #Fn+2=Fn+1 + Fn#
            F_2=F_1
            F_1=som
        return(som)

def Fibo_rec(n):
    if n==0: #Close d'arrêt récursive#
        return(0)
    elif n==1: #Close d'arrêt récursive#
        return(1)
    else:
        return(Fibo_rec(n-1)+Fibo_rec(n-2)) #Empiler et dépiler#

start=time()
rep=10
it=[]
for k in range(rep):
    Fibo(k) #Calculs des premiers termes de la suite#
    end=time()-start
    it.append(end) #Stockage des temps de calculs#
rec=[]
for i in range(rep):
    Fibo_rec(i)
    end=time()-start
    rec.append(end)
import matplotlib.pyplot as plt
ab=range(rep)
plt.plot(ab, rec, color="b", label="Version recursive")
plt.plot(ab, it, color="r", label="Version iterative")
plt.legend(loc=2) #Affichage de la légende en haut à gauche#
plt.show()

Bon j'ai testé avec d'autres fonctions et j'ai ajouté une moyenne et j'ai augmenté le nombre de répétition à 15 et j'ai un graphique correct :

# https://www.jeuxvideo.com/forums/42-47-65632835-1-0-1-0-comparaison-vitesses-d-executions-algorithmes-recursif-et-iteratif-en-python.htm
# fibonacci_benchmarks.py

from __future__ import unicode_literals

from time import time

import matplotlib.pyplot as plt


def Fibo(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a


def Fibo_rec(n):
    if n <= 1:
        return n
    else:
        return(Fibo_rec(n-1) + Fibo_rec(n-2))


rep = 15

it = []
start = time()

for k in range(0, rep):
    Fibo(k)  # Calculs des premiers termes de la suite#
    duration = time() - start
    moyenne = duration / (k+1)
    it.append(moyenne)  # Stockage des temps de calculs#

rec = []
start = time()

for i in range(0, rep):
    Fibo_rec(i)
    duration = time() - start
    moyenne = duration / (k+1)
    rec.append(moyenne)

ab = range(rep)
plt.plot(ab, rec, color="b", label="Version recursive")
plt.plot(ab, it, color="r", label="Version iterative")
plt.legend(loc=2)  # Affichage de la légende en haut à gauche#
plt.show()

Sur ta courbe la fonction récursive devient plus lente que la fonction itérative dès la troisième itération. Sur la mienne c’est après la 6eme itération.

Je ne sais pas si c'est lié à la machine ou à l'architecture système ou la version de python employée.

Ce que tu veux est mersurer le temps de chaque appel, pas mesurer le temps depuis le debut.

@godrik, exact, en mettant le start dans la boucle comme je l'avais dit au début ça fonctionne correctement. Je ne sais ps pourquoi il m'a dit que ça ne fonctionnait pas

Pour avoir toutes les valeurs en abscisses :

ab = range(rep)
plt.plot(ab, rec, color="b", label="Version recursive")
plt.plot(ab, it, color="r", label="Version iterative")
plt.xticks(ab)
plt.legend(loc=2)  # Affichage de la légende en haut à gauche#
plt.show()

En fait les deux méthodes (mettre start à l'intérieur de la boucle et à l'extérieur) sont intéressantes : pour l'une mettre en évidence les points négatifs des piles et de la récursivité (qui peuvent être évités avec la mémoïsation) et l'autre en tenant compte simplement de manière globale (sans tenir compte des problèmes de la récursivité) la rapidité de l'algo.
Cependant j'ai copier coller ton algo et ça m'affiche toujours la même courbe que ça soit sur Spyder dans Anaconda ou avec Python 3.9.1. Même en redémarrant le noyau ça ne change pas.... C'est très étrange...

Voici le code que j'ai testé :

# https://www.jeuxvideo.com/forums/42-47-65632835-1-0-1-0-comparaison-vitesses-d-executions-algorithmes-recursif-et-iteratif-en-python.htm
# fibonacci_benchmarks.py

from __future__ import unicode_literals

from time import time

import matplotlib.pyplot as plt


def Fibo(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a


def Fibo_rec(n):
    if n <= 1:
        return n
    else:
        return(Fibo_rec(n-1) + Fibo_rec(n-2))


rep = 10

it = []

for k in range(0, rep):
    start = time()
    Fibo(k)  # Calculs des premiers termes de la suite#
    duration = time() - start
    it.append(duration)  # Stockage des temps de calculs#

rec = []
start = time()

for i in range(0, rep):
    start = time()
    Fibo_rec(i)
    duration = time() - start
    rec.append(duration)

ab = range(rep)
plt.plot(ab, rec, color="b", label="Version recursive")
plt.plot(ab, it, color="r", label="Version iterative")
plt.xticks(ab)
plt.legend(loc=2)  # Affichage de la légende en haut à gauche#
plt.show()

Tape directement dans ton terminal (ou invite de commande sous windows, assure toi de bien utiliser python 3) :

python fibonacci_benchmarks.py

Tu peux faire python --version pour connaître ta version de Python.

Pour avoir un graphique correspondant à celui posté au début :

ab = range(rep)
plt.plot(ab, rec, color="b", label="Version recursive")
plt.plot(ab, it, color="r", label="Version iterative")
plt.xticks(ab)  # Affichage de toutes les valeurs de x
plt.margins(x=0)  # Enlève la marge sur l'axe des abscisses
plt.ticklabel_format(style="plain")  # Enlève la notation scientifique
plt.legend(loc=2)  # Affichage de la légende en haut à gauche#
plt.show()

Donc j'ai suivi tes instructions à la lettre et cela me renvoie seulement la courbe itérative constante. J'utilise bien python 3.9.1 et Windows 10. Ca ne m'était jamais arrivé auparavant... Je pense que le problème vient du module time sur mon PC. Ca serait possible ?

Le 04 février 2021 à 17:50:22 Info_maths a écrit :
Donc j'ai suivi tes instructions à la lettre et cela me renvoie seulement la courbe itérative constante. J'utilise bien python 3.9.1 et Windows 10. Ca ne m'était jamais arrivé auparavant... Je pense que le problème vient du module time sur mon PC. Ca serait possible ?

Non, je viens de tester avec Python 3.9.0 et ça fonctionne également. Éventuellement, désinstalle et réinstalle matplotlib.

C'est peut être dû à la taille de la pile, comme c'est une fonction récursive il y a peut être trop d'appels et ça plante. Mais dans ce cas on aurait une RecursionError...

Je viens de désinstaller et réinstaller matplotlib via l'invite de commande. Il m'a proposé de mettre à jour le module après re installation et je suis passé à la version 21.0.1. J'ai relancé python 3.9.1 et ai lancé ce code :

from __future__ import unicode_literals
from time import time
import matplotlib.pyplot as plt

def Fibo(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a


def Fibo_rec(n):
    if n <= 1:
        return n
    else:
        return(Fibo_rec(n-1) + Fibo_rec(n-2))


rep = 10
start=time()
it = []

for k in range(0, rep):
    start = time()
    Fibo(k)  # Calculs des premiers termes de la suite#
    duration = time() - start
    it.append(duration)  # Stockage des temps de calculs#

rec = []
start = time()
for i in range(0, rep):
    start = time()
    Fibo_rec(i)
    duration = time() - start
    rec.append(duration)

ab = range(rep)
plt.plot(ab, rec, color="b", label="Version recursive")
plt.plot(ab, it, color="r", label="Version iterative")
plt.xticks(ab)  # Affichage de toutes les valeurs de x
plt.margins(x=0)  # Enlève la marge sur l'axe des abscisses
plt.ticklabel_format(style="plain")  # Enlève la notation scientifique
plt.legend(loc=2)  # Affichage de la légende en haut à gauche#
plt.show()

Et cela me renvoie :

Extrêmement bizarre...