Souvent, lorsque du développement d'une fonction ou de manière générale d'un logiciel, on ne se soucie pas forcement de l'optimisation des boucles (for, while, etc..) que l'on peut être amenés à mettre en place. Or cela peut permettre d'améliorer de manière significatives les performances du programme en question.
Nous allons prendre comme exemple, pour illustrer ce problème, les nombres premiers et utiliser Python comme langage de programmation.
Les boucles sont omniprésentes dans les languages de programmation par l'intermédiare des structures de controles que sont les instructions for, while, do..while, etc... . Un boucle est donc un moyen d'effectuer un certain nombre de fois une opération avec entre chaque boucle plus ou moins de changement. Par exemple dans le cas de la recherche des nombres premiers, on boucle sur tous les nombres entre 2 et le nombre en question avec comme opération un test de primalité sur le nombre courant.
Un nombre premier est un entier naturel strictement supérieur à 1, divisible seulement par 1 et par lui-même. Les vingt premiers nombres premiers sont pax exemple: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 (Source Wikipédia)
De manière simple, pour savoir si est nombre est premier, nous allons tester :
Nous allons donc mettre en place une fonction (ici en Python) qui permet de définir un nombre est premier.
def estPremier(nombre):
estPrem = 1
# le nombre est-il supérieur à 1
if (nombre <= 1):
estPrem = 0
else :
# On divise le nombre par tous les nombres entre 2 et lui-même
for i in range(2,nombre):
if ((nombre%i)==0):
# s'il est divisible, alors il n'est pas premier
estPrem = 0
return estPrem
Dans l'exemple précédent on calcul pour tous les nombre entre 2 et n (le nombre dont on veut déterminer s'il est premier). On effectue ainsi un grand nombre de calcul inutile si dès le début, on trouve que le nombre n'est pas premier.
Par exemple lorsque l'on test le nombre 3000, dès que l'on teste la division de 3000 par 3 on peut savoir que le nombre n'est pas premier. On peut donc sortir de la boucle immédiatement.
Voici la fonction corrigée :
def estPremier(nombre):
estPrem = 1
# le nombre est-il supérieur à 1
if (nombre <= 1):
estPrem = 0
else :
# On divise le nombre par tous les nombres entre 2 et lui-même
for i in range(2,nombre):
if ((nombre%i)==0):
# s'il est divisible, alors il n'est pas premier
estPrem = 0
# Si il n'est pas premier, on sors de la boucle sans
# tester les nombres suivants
break
return estPrem
On pourrait se dire qu'avec la vitesse de calcul que possède les ordinateurs actuels, il est inutile perdre son temps en optimisation. Mais comme il est possible de le voir avec les chiffres suivants, la différence au niveau de la vitesse d'exécution entre les deux fonctions est loin d'être négligeable.
Voici par exemple le temps qu'a nécessite l'exécution pour le calcul de primarité pour les nombres de 1 à 5000:
sans optimisation : 6.30 secondes
avec optimisation : 1.12 secondes
Le gain de vitesse est donc de 562,3%. Bien sur nous sommes ici dans un cas bien particulier avec un grand nombre de boucle, mais c'est justement ce qui nous permet de mettre en évidence l'importance de sortir d'une boucle.
Retour à la liste des articles