| ★ CODING ★ HEBDOGICIEL ★ COURS D'ASSEMBLEUR|HEBDOGICIEL n°82) ★ |
| La page pédagogique d'hebdogiciel 082: Generalite sur les Routines | Coding Hebdogiciel |
La page pédagogique d'hebdogiciel : Formation à l'assembleurReste à définir ce qui rend une routine meilleure qu'une autre Cette énigme se résoud relativement simplement en se basant sur des notions élémentaires de logique. Je ne vous bassinerai pas le cerveau de démonstrations mathématiques absconses, aussi je me contenterai de vous énoncer les résultats qui servent de base de jugement et de choix entre deux programmes équivalents Trois critères sont généralement retenus pour effectuer un choix de ce genre. Nous allons les définir maintenant pour mieux pouvoir nous rendre compte de ce qu'est le jugement théorique d'un algorithme Nous allons supposer que nous disposons de deux routines parfaitement équivalentes dans le rôle, mais programmées de manière rigoureusement différente.
1. Rapidité : ce critère de choix ne pose pas de problème fondamental pour le mettre en application. Pour connaître la rapidité d'une routine, deux méthodes sont applicables, lune souffrant d'imprécision l'autre étant plus longue à mettre en œuvre pour des programmes importants. a. méthode empirique : pour connaître la rapidité relative d'une routine par rapport à l'autre, nous pouvons tout simplement chronométrer le temps d'exécution de chacune d'elles et comparer le temps mis pour arriver au résultat. Si cette méthode ne présente aucune complication de réalisation, par contre elle ne sera jamais suffisamment précise pour les puristes. Pour eux nous allons voir l'autre méthode. b. méthode théorique : à chaque instruction, pour un micro-processeur donné, correspond un certain nombre de cycles d'horloge. Supposons que l'horloge de votre micro tourne à 1 Mégahertz. Une impulsion est émise par l'horloge tous les millionièmes de seconde. Suivant les micro-processeurs, un cycle dure une, deux, trois ou deux impulsions et demie (par exemple). Bref ce nombre d'impulsions est déterminé par le constructeur du micro-ordinateur. A partir de là vous disposez d'une unité de mesure, le cycle, et d'une certaine séquence d'instructions dont chacune dure un nombre déterminé de cycles. Vous pouvez donc facilement, en décomptant le nombre de cycles, connaître la durée d'exécution d'une routine. Même si cette méthode est la seule parfaitement rigoureuse, elle ne sera simple à appliquer que pour les routines courtes. 2 Occupation mémoire : encore une fois, cette idée-la ne parait pas trop complexe a analyser Maigre tout il est nécessaire de la subdiviser en deux parties si l'on veut disposer d un argument valable pour le choix final entre les deux routines a. Longueur du programme il s'agit simplement de connaître
En fin de course nous aurons donc pour chacune des routines un nombre total d'octets nécessaires au bon fonctionnement de chacune d'elles. 3 Complexité de l'algorithme O = n x (nombre de boucles) O = n ! 2 Admettons maintenant que votre routine compte huit boucles dont quatre sont imbriquées les unes dans les autres et dont les quatre autres sont simples. Nous nous trouverons dans le cas dune routine de complexité égale à : O =(n ^ 4) + (4 x n) C'est maintenant que le goût prononcé des mathématiciens pour la simplification intervient Ainsi lorsque n est très grand (ce qui suppose que la routine aura de nombreuses données a traiter), la valeur de (4 x n) devient négligeable face a la valeur (n ^ 4). Essayez d'effectuer ce calcul avec n égal a 10. 100 et 1000 Dans ce cas. nous pourrons dire (en ne faisant que mettre nos pas dans ceux d illustres prédécesseurs) que la complexité de la routine sera (après simplification et approximativement) : O = n ^ 4 Le choix final entre les deux routines se passera donc de la manière suivante 1 routine la pus rapide Il est bien entendu très rare qu'une même routine soit maîtresse pour les trois critères . Il s'agira alors d'effectuer la sélection en fonction de l'application a laquelle est destinée la routine. Si elle ne doit traiter qu'un petit nombre de données, les deux premiers critères seront prépondérants sur le troisième En revanche si cette routine doit tourner longtemps, vous devrez vous méfier de la complexité de l'algorithme car c'est lui qui déterminera de façon certaine la rapidité d'exécution de la routine. Mais tout ce qui précède dans le choix entre les routines relevé plus de la théorie que de la pratique. En général, ce qui conduit a choisir une routine plutôt que l'autre se résume de la façon suivante la meilleure sera la plus équilibrée des deux routines en compétition Par équilibrée, j'entends celle qui ne sera pas trop lente et qui n occupera pas trop de place mémoire tout en travaillant sur l'algorithme le moins complexe possible. Bien sûr l'importance de chaque critère par rapport aux autres n'est qu'une question d'environnement. Si vous disposez de 256 Ko de mémoire, le critère concernant l'occupation mémoire deviendra moins important, les deux autres devenant prioritaires Malgré tout il reste essentiel de se rapprocher d'un idéal tel que l'algorithme soit de complexité avec une occupation mémoire minimale et un temps d'execution ridiculement court Le fait de se rapprocher de ce modèle s'appelle l optimisation d'un programme. Un même programme optimise par deux programmeurs différents donnera un listing a l'arrivée fort différent C'est a ce moment-la que les trois critères de choix pourront s appliquer au mieux pour la sélection du meilleur programme Vous vous rendez compte que ce genre de sélection n'a d'importance qu'à partir du moment où vos routines sont si nombreuses qu'une organisation rigoureuse devient nécessaire pour la bonne marche de l'ensemble de celles-ci. Mais qu'est-ce qu'une routine, allez-vous me dire. Remontons un peu en arrière dans ce cours. Lors d'une série de conseils sur la démarche à suivre pour la construction d'un algorithme, je vous avais fortement suggéré de subdiviser votre problème en un ensemble de petits problèmes indépendants. Chacun de ces petits problèmes peut, si vous structurez correctement votre raisonnement, donner naissance à un sous-programme spécifique. Tout comme dans tous les langages évolués, l'assembleur permet d'effectuer des appels à des sous-programmes, et c'est ces sous-programmes que nous avons l'habitude de nommer routines. D'ailleurs, nous allons traiter brièvement certains des problèmes posés par les appels aux routines en cours de programme. HEBDOGICIEL n°82 - 10 mai 1985
|
