Evaluation de temps d’exécution

1 – Création de tableaux aléatoires d’entiers

Création d’un tableau t de valeurs aléatoires à trier

t=[]
n=10
Max=10
for i in range(n):
    t.append(random.randint(0,Max))

Mesure de la durée d’exécution d’un programme

debut=time.time()
t=[]
for i in range(100000):
    t.append(random.randint(0,10))
duree=time.time()-debut
print(duree)

A quoi correspond la variable debut ? Effectuez un test pour justifier la réponse.

La variable debut correspond à

Tracer un nuage de points

Exemple 10 points de la droite d’équation y=-2x+10

import matplotlib.pyplot as plt
x=[i for i in range(10)]
y=[-2*xval+10 for xval in x]
plt.scatter(x,y)
plt.show()

Visualiser la duree de création d’un tableau en fonction de sa longueur n

import matplotlib.pyplot as plt
import time
import random
def duree_tableau_alea2(n):
    t=[]
    debut=time.time()
    for i in range(n):
        t.append(random.randint(0,10))
    duree=time.time()-debut
    return duree
x=[i*10**5 for i in range(10)]
y2=[duree_tableau_alea2(val) for val in x]
plt.scatter(x,y2)
plt.show()

Comparaisons et options pour le tracé

import time
import matplotlib.pyplot as plt
import numpy as np
import random
def duree_tableau_alea(n):
    debut=time.time()
    t=[random.randint(0,10) for i in range(n)]
    duree=time.time()-debut
    return duree
def duree_tableau_alea1(n):
    debut=time.time()
    t=list(np.random.randint(10,size=n))
    duree=time.time()-debut
    return duree
def duree_tableau_alea2(n):
    t=[]
    debut=time.time()
    for i in range(n):
        t.append(random.randint(0,6))
    duree=time.time()-debut
    return duree
x=[(i)*10**5 for i in range(5)]
y=[duree_tableau_alea(val) for val in x]
y1=[duree_tableau_alea1(val) for val in x]
y2=[duree_tableau_alea2(val) for val in x]
plt.scatter(x,y, color='coral', linestyle='solid', label='liste en compréhension')
plt.scatter(x,y1, color='navy', linestyle='solid', label='tableau numpy')
plt.scatter(x,y2, color='green', linestyle='solid', label='liste avec append')
ax = plt.gca()
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.xaxis.set_ticks_position('bottom')
ax.spines['bottom'].set_position(('data',0))
ax.yaxis.set_ticks_position('left')
ax.spines['left'].set_position(('data',0))
plt.title('durée de céation d''un tableau de n valeurs aléatoires ',color="navy", fontsize=12)
ax = ax.set(xlabel='n ', ylabel='durée (en s)')
plt.legend(loc='center right');
plt.show()

2. Comparaison de tris

A vous de tester annoter et comprendre voire modifier le code ci-dessous

import time
import matplotlib.pyplot as plt
import numpy as np
import random
def tri_insertion(tableau):
    for i in range(1,len(tableau)):
        en_cours = tableau[i]
        j = i
        #décalage des éléments du tableau }
        while j>0 and tableau[j-1]>en_cours:
            tableau[j]=tableau[j-1]
            j = j-1
        #on insère l'élément à sa place
        tableau[j]=en_cours  
        
def tri_selection(tableau):
    nb = len(tableau)
    for en_cours in range(0,nb):    
        plus_petit = en_cours
        for j in range(en_cours+1,nb) :
            if tableau[j] < tableau[plus_petit] :
                plus_petit = j
        if min is not en_cours :
            temp = tableau[en_cours]
            tableau[en_cours] = tableau[plus_petit]
            tableau[plus_petit] = temp
def duree_tris(n):
    t1=list(np.random.randint(10,size=n))
    t2=t1.copy()
    t3=t1.copy()
    debut=time.time()
    tri_selection(t1)
    duree_selection=time.time()-debut
    debut=time.time()
    tri_insertion(t2)
    duree_insertion=time.time()-debut
    debut=time.time()
    t3.sort()
    duree_sort=time.time()-debut
    return duree_selection,duree_insertion,duree_sort
x=[(i)*10**3 for i in range(10)]
y=[duree_tris(val) for val in x]
y1=[y[i][0] for i in range(10)]
y2=[y[i][1] for i in range(10)]
y3=[y[i][2] for i in range(10)]
plt.scatter(x,y1, color='navy', linestyle='solid', label='tri selection')
plt.scatter(x,y2, color='green', linestyle='solid', label='tri insertion')
plt.scatter(x,y3, color='red', linestyle='solid', label='tri sort')
ax = plt.gca()
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.xaxis.set_ticks_position('bottom')
ax.spines['bottom'].set_position(('data',0))
ax.yaxis.set_ticks_position('left')
ax.spines['left'].set_position(('data',0))
plt.title('durée pour trier un tableau de n valeurs aléatoires ',color="navy", fontsize=12)
ax = ax.set(xlabel='n ', ylabel='durée (en s)')
plt.legend(loc='upper left');
plt.show()
print(y1)
print(y2)
print(y2)

https://colab.research.google.com/drive/16lRvI9-Ia1uogkhjSRY6kn4zlyj0a9Kc?hl=fr#scrollTo=xEfuhoufnmTw