Titre: Informatique MP Arago
Auteurs: Ph. Langlois
Ecole: Néant
Résumé: Mesurer le temps d’exécution d’un programme sur une machine actuelle est une une tâche beaucoup plus ardue qu’il n’y parait. En effet, l’impression que l’exécution de votre programme mobilise à elle seule les ressources de votre ordinateur est une illusion. Le temps que vous attendez pour obtenir votre résultat, même si cela vous parait instantané, est en fait partagé : pendant ce même temps, votre ordinateur effectue certainement de nombreuses autres tâches, par exemple liées au système d’exploitation, aux périphériques, à d’autres utilisateurs si votre machine gère plusieurs sessions, par ailleurs, les unités de calculs et l’organisation (des niveaux) de la mémoire compliquent très fortement la mesure fiable des temps d’exécution et leur analyse.
En pratique, plus ce que vous voulez mesurer est court, plus la mesure sera incertaine et non reproductible. Pour ce qui nous intéresse, l’obtention d’une mesure significative consistera à répéter l’exécution dans une boucle, de mesurer le temps d’exécution de cette boucle et d’en retenir la moyenne. Il n’est pas inutile de répéter ce type de mesures et le cas échéant de traiter l’échantillon obtenu.
Les “gros problèmes” sont aussi sujets à remarque. Des tailles de données importantes nécessitent un volume important de transferts entre la mémoire et les unités de calcul. Ces transferts sont complexes et leurs temps est, d’une part non linéaire par rapport à la taille des données, et d’autre part beaucoup plus important que les temps de calcul souvent associés. A titre indicatif, il y a une facteur 10 entre ce temps de transfert et le temps d’un calcul arithmétique élémentaire. Ainsi, les mesures peuvent être surprenantes lorsqu’elles deviennent “dominées” par ces temps de transfert. Le modèle de nos analyses de la complexité des algorithmes ne prend pas en compte cet aspect très difficile.
Pour finir, ceci illustre la différence entre les propriétés d’un algorithme et celles de ses mises en œuvre et, par la même occasion, confirme l’intérêt des notations asymptotiques O, _, dont on a souvent signalé qu’elles masquent pas mal de détails…
Extrait du sommaire:
1 Rappels de Python
2 Tracer et mesurer des performances
3 Exercices
4 Remise en jambe et récursivité
5 Les piles
6 Trier
7 Couleurs, images et traitements
8 Devoir maison
Obtenir le fichier PDF: Informatique MP