LES FICHIERS
Les fichiers
ont pour avantage d'être dynamiques (la taille peut varier ou du moins
augmenter au cours de l'utilisation, du moins tant qu'il reste de la place sur
le support), et de ne pas être volatiles comme l'est la mémoire
(c'est à dire que les informations restent présentes en l'absence
d'alimentation électrique). Leur principal inconvénient est le
temps d'accès à une donnée (de l'ordre de 106
fois plus lent que la mémoire, en général plus de 10 ms
pour un disque dur, mais jusqu'à plusieurs secondes pour une bande
magnétique). L'insertion et la suppression d'éléments
autre part qu'en fin d'un fichier est quasiment impossible, en
général on devra passer par la création d'un nouveau
fichier, y recopier le début du fichier initial jusqu'à la
modification prévue, puis écrire les données
modifiées puis recopier le reste du fichier. Les fichiers peuvent
être séquentiels ou à accès direct.
Un fichier séquentiel
permet uniquement d'accéder aux données dans l'ordre de leur
écriture. L'exemple le plus courant est la bande magnétique (ou
streamer ou DAT). On n'utilise plus que rarement les fichiers stockés
sur bande directement dans les programmes : du fait des possibilités des
disques durs (jusqu'à plusieurs Giga-octets), on préfère
utiliser des fichiers à accès direct, et les sauvegarder sur
bande (séquentiellement) une fois le traitement terminé.
Certaines grosses applications nécessitent néanmoins des
traitements directement sur bandes magnétiques, il faut alors choisir
les algorithmes en conséquence (en général dans ces cas on
utilisera au moins deux lecteurs de bandes, un pour le fichier initial, un pour
le fichier traité), en choisissant plus particulièrement des
algorithmes divisant le fichier en sous-fichiers qui eux tiendront en
mémoire centrale et pourront être traités plus rapidement
(par exemple pour les tris, on utilisera par exemple un tri par fusion,
surtout si l'on dispose de trois lecteurs : deux pour les sous fichiers
à fusionner, le troisième pour le fichier final). Le grand
avantage du fichier séquentiel est qu'il peut contenir des
données de tout type, de taille différente (c'est
désormais la seule raison de son utilisation). Pour stocker un
graphique, on pourra enregistrer le nombre de segments, puis les
caractéristiques de chacun des segments, puis le nombre d'arcs de
cercles, puis leurs caractéristiques,...
On classe souvent sous la dénomination de fichiers séquentiels
les fichiers de texte : se sont en fait souvent des fichiers à
accès direct aux caractères (on peut accéder directement
au Nième caractère), mais en fait l'accès est
séquentiel au niveau des lignes : pour accéder à la
Nième ligne, il faut lire le fichier depuis le début,
jusqu'à compter N-1 signes de fin de ligne. Les fichiers de texte
peuvent également être utilisés pour stocker des valeurs
numériques : les nombres sont alors formatés pour être
écrits en décimal à l'aide de caractères ASCII, et
peuvent donc directement être imprimés ou réutilisés
par un autre programme ou sur une autre machine, alors que la sauvegarde
directe d'une valeur numérique est faite en binaire (recopie des 0 et 1
en mémoire), ce qui prend moins de place mais n'est plus lisible que par
un programme qui utilise le même format.
Les fichiers séquentiels ne peuvent en général pas
être modifiés, la seule possibilité étant l'ajout
derrière les données déjà stockées (pour un
fichier texte, sur disque, on peut remplacer des caractères mais pas en
ajouter ni en supprimer sauf en fin de fichier).
Un fichier à accès direct
correspond à un tableau en mémoire : toutes ses composantes ont
la même taille, on peut donc accéder directement à la
Nième. Comme pour un tableau, les insertions
et suppressions
nécessitent des décalages des composantes suivantes, ce qui est
en général trop long pour être envisageable. Ceci exclut
donc l'utilisation de tout algorithme utilisant l'insertion (le tri par
insertion par exemple), mais aussi ceux qui déplacent des
éléments sans les positionner à leur place
définitive (le tri bulle par exemple). Une méthode de tri sera
par exemple un tri par sélection et création d'un nouveau
fichier. L'accès au données devra être optimisé : on
préférera bien évidement la dichotomie
à la recherche
séquentielle, et même on préférera une dichotomie
pondérée (avec estimation par calcul de la position probable),
puisque tout calcul sera beaucoup plus rapide qu'une lecture dans le fichier.
Un fichier à accès direct peut également être
utilisé pour stocker et traiter des listes, arbres ou graphes : on
utilise la méthode du super-tableau : chaque élément est
numéroté, en fonction de sa position dans le fichier, les liens
étant ces numéros. Il faut bien garder à l'esprit qu'il ne
faut jamais stocker sur fichier un pointeur : l'adresse où a
été mise la valeur pointée a peu de chances d'être
la même à la prochaine utilisation du programme. Ils est alors
toujours nécessaire de numéroter les composantes et remplacer les
pointeurs par le numéro de la valeur pointée avant de faire une
sauvegarde sur fichier.
La méthode souvent la plus efficace pour l'utilisation de
fichiers séquentiels est l'indexation
(elle est également utilisable pour les autres types de données,
stockées en mémoire). Les composantes sont stockées dans
le fichier dans l'ordre de leur création. On utilise alors un tableau
d'index, donnant en première position le numéro de la
première composante, puis de la seconde,... L'avantage de cette
méthode est que l'ajout de composantes est optimal : on rajoute la
valeur en fin de fichier, on met à jour le tableau d'index.
Tout déplacement d'une composante sera donc remplacé par une
modification du tableau d'index, sans déplacement réel de la
valeur dans le fichier. En général, ce tableau peut tenir en
mémoire, ce qui permet une modification rapide, en général
on préfère le sauver également sur support
magnétique avant de quitter le programme, ce qui évitera de le
recréer (par exemple refaire un tri) à la prochaine utilisation.
On peut également utiliser une liste d'index si les déplacements
sont fréquents (mais alors l'accès devient séquentiel). Le
second avantage de cette méthode est que l'on peut utiliser
simultanément plusieurs index : par exemple pour une liste de personnes,
on peut créer un index pour le classement alphabétique des noms,
un autre sur les villes, on accédera donc plus rapidement à tous
les champs indexés, alors que les champs non indexés devront se
satisfaire d'une recherche séquentielle, et ce sans modification dans le
fichier (un tri par nom puis par ville auraient été
nécessaires sans indexation). Par contre toute modification
nécessitera la mise à jour de tous les tableaux d'index. Exemple:
La suppression, par contre, pose problème. En
général, toujours pour éviter les décalages dans
les fichiers, on préfère marquer d'un signe distinctif les champs
supprimés (par exemple un nom non alphabétique ou vide), puis
remettre à jour les index qui ne pointeront plus sur ce champ. Le
retassage, assez long, n'est effectuée que sur ordre de l'utilisateur ou
lorsqu'il quitte le programme. On peut aussi (comme dans la méthode du
super-tableau) créer une liste des champs vides, ce qui permettra d'y
accéder, plus rapidement que par une recherche séquentielle, lors
de la prochaine insertion.
Sur un fichier indexé, on peut à nouveau se permettre des
algorithmes utilisant l'insertion, puisque celle-ci n'affecte que l'index
(à accès rapide). Pour un tri par exemple, on pourra utiliser le
tri par insertion,
à condition d'optimiser la recherche de la position d'insertion (par
dichotomie pondérée par exemple), puisque celle-ci
nécessite des lectures de champs dans le fichier alors que l'insertion
n'entraîne que des décalages dans un tableau, d'une durée
généralement négligeable devant le temps pris par la
recherche. On peut également utiliser une liste d'index plutôt
qu'un tableau si nécessaire.