Les abstractions que l'on manipule dans un programme par l'intermédiaire des variables permettent de concevoir, comprendre, vérifier les programmes sur la base des lois qui gouvernent les abstractions.
Exemple : un programme manipulant les abstractions de nature économique peut être entièrement conçu, compris et vérifié en considérant uniquement des lois économiques).
Cependant, si la connaissance exacte des principes de fonctionnement
d'un ordinateur ou d'un langage n'est pas indispensable (sauf pour les
professionnels que sont les informaticiens), il est bon d'avoir ponctuellement
une idée plus précise de comment un programme écrit
dans langage s'exécute en machine. Dans le domaine qui nous
intéresse, ici les structures de données, il est important
de savoir comment sont représentées des structures fondamentales
telles que :
Le problème de la représentation des structures de données revient à faire correspondre, à l'abstraction que représente la structure, une organisation particulière de la mémoire centrale de la machine. En première approximation, la mémoire centrale d'une machine est un tableau de cellules élémentaires appelées mots. Les indices de ces mots sont appelés adresses.
var Memoire : array [Adresses] of Mots;
Les cardinalités d'adresses et de mots varient fortement d'une machine à l'autre. Par exemple :
quelques milliers < card(Adresse) < plusieurs millions
La conversion indice Æ adresse pour la j-ème composante d'un tableau s'effectue de la manière suivante :
i = i0 + (j-1) * S
avec : i0 = adresse de la première composante
S = nombre de mots qu'occupe une
composante (ce nombre peut être fractionnaire)
Le cas idéal serait : S = 1, mais ce n'est pas souvent le cas; alors S est arrondi à l'entier supérieur le plus proche. Donc, chaque composante occupera S' mots, avec S'-S laissé inoccupé.
Cette méthode, qui consiste à arrondir le nombre exact de mots nécessaires à l'entier supérieur, est appelée remplissage (padding).
Exemple
Fig. .3.1 Remplissage
Le facteur d'utilisation est donné par :
U = S / S'
l'objectif étant d'avoir un facteur n aussi proche que possible de
1. Notons que :
U > 0,5 si S > 0,5 mot
Cependant, si S
0,5,
le facteur d'utilisation peut être largement amélioré
si l'on met plusieurs
composantes du tableau dans un seul mot. Cette méthode est appelée
compactage : si n composantes sont compactées
dans un seul mot, le facteur d'utilisation est :
U = (n * S) / (n * S)' avec (n*S)' = 1 géné
Exemple
Fig. 3.2. Compactage
L'accès à la j-ème composante d'un tableau compacté
suppose :
Ce compactage, l'utilisateur doit pouvoir l'exiger si nécessaire sans avoir à se préoccuper de son mécanisme. C'est pourquoi le langage Pascal introduit deux variantes aux structures tableaux et enregistrements qui sont :
packed array [...]
packed record ...
Exemple (chaînes de longueur fixe)
type alfa = packed array [1..n] of char;
Si la structure occupe moins de place en mémoire, ses composantes deviennent, par contre, plus difficiles d'accès. Pour un tableau compacté, en Pascal, il faudra passer par les procédure pack et unpack pour manipuler les composantes individuelles; par contre, on pourra utiliser l'affectation sur le tableau complet.
C'est pour des raisons de compromis entre efficacité d'implantation et occupation en mémoire que les structures compactées ont la contrainte de ne pas avoir de composante de taille inférieure à un mot machine qui soit à cheval sur deux mots machine. C'est pourquoi il est généralement exigé que dans l'exemple vu plus haut, n soit un nombre entier.
Les différentes composantes d'un enregistrement sont stockées les unes à la suite des autres. Dans un enregistrement non paqueté, chaque composante doit commencer au début d'un nouveau mot machine. Pour les mêmes raisons de compromis entre efficacité du code et occupation de la mémoire, dans un enregistrement paqueté, les composantes de taille supérieure à un mot doivent commencer au début d'un mot et seules les composantes de taille inférieure à un mot pour lesquelles il y aurait encore de la place dans le dernier mot utilisé se ront placées au milieu d'un mot (pas de composante à cheval sur deux mots). On emploie donc simultanément les techniques de remplissage et de compactage.
Pour un enregistrement, il n'y a pas de changement dans l'utilisation (pas de décompactage nécessaire), seul le temps d'accès sera plus long, car le compilateur devra générer un code plus complexe pour accéder à l'information.
Exemple
Fig. 3.3. Enregistrement paqueté.
4. Les
types abstraits.
Site Hosting: Bronco
Table des
matières.