LES FICHIERS
Les fichiers
ont pour avantage d'etre 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 etre volatiles comme l'est la memoire
(c'est a dire que les informations restent presentes en l'absence
d'alimentation electrique). Leur principal inconvenient est le
temps d'acces a une donnee (de l'ordre de 106
fois plus lent que la memoire, en general plus de 10 ms
pour un disque dur, mais jusqu'a plusieurs secondes pour une bande
magnetique). L'insertion et la suppression d'elements
autre part qu'en fin d'un fichier est quasiment impossible, en
general on devra passer par la creation d'un nouveau
fichier, y recopier le debut du fichier initial jusqu'a la
modification prevue, puis ecrire les donnees
modifiees puis recopier le reste du fichier. Les fichiers peuvent
etre sequentiels ou a acces direct.
Un fichier sequentiel
permet uniquement d'acceder aux donnees dans l'ordre de leur
ecriture. L'exemple le plus courant est la bande magnetique (ou
streamer ou DAT). On n'utilise plus que rarement les fichiers stockes
sur bande directement dans les programmes : du fait des possibilites des
disques durs (jusqu'a plusieurs Giga-octets), on prefere
utiliser des fichiers a acces direct, et les sauvegarder sur
bande (sequentiellement) une fois le traitement termine.
Certaines grosses applications necessitent neanmoins des
traitements directement sur bandes magnetiques, il faut alors choisir
les algorithmes en consequence (en general dans ces cas on
utilisera au moins deux lecteurs de bandes, un pour le fichier initial, un pour
le fichier traite), en choisissant plus particulierement des
algorithmes divisant le fichier en sous-fichiers qui eux tiendront en
memoire centrale et pourront etre traites 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
a fusionner, le troisieme pour le fichier final). Le grand
avantage du fichier sequentiel est qu'il peut contenir des
donnees de tout type, de taille differente (c'est
desormais la seule raison de son utilisation). Pour stocker un
graphique, on pourra enregistrer le nombre de segments, puis les
caracteristiques de chacun des segments, puis le nombre d'arcs de
cercles, puis leurs caracteristiques,...
On classe souvent sous la denomination de fichiers sequentiels
les fichiers de texte : se sont en fait souvent des fichiers a
acces direct aux caracteres (on peut acceder directement
au Nieme caractere), mais en fait l'acces est
sequentiel au niveau des lignes : pour acceder a la
Nieme ligne, il faut lire le fichier depuis le debut,
jusqu'a compter N-1 signes de fin de ligne. Les fichiers de texte
peuvent egalement etre utilises pour stocker des valeurs
numeriques : les nombres sont alors formates pour etre
ecrits en decimal a l'aide de caracteres ASCII, et
peuvent donc directement etre imprimes ou reutilises
par un autre programme ou sur une autre machine, alors que la sauvegarde
directe d'une valeur numerique est faite en binaire (recopie des 0 et 1
en memoire), ce qui prend moins de place mais n'est plus lisible que par
un programme qui utilise le meme format.
Les fichiers sequentiels ne peuvent en general pas
etre modifies, la seule possibilite etant l'ajout
derriere les donnees deja stockees (pour un
fichier texte, sur disque, on peut remplacer des caracteres mais pas en
ajouter ni en supprimer sauf en fin de fichier).
Un fichier a acces direct
correspond a un tableau en memoire : toutes ses composantes ont
la meme taille, on peut donc acceder directement a la
Nieme. Comme pour un tableau, les insertions
et suppressions
necessitent des decalages des composantes suivantes, ce qui est
en general trop long pour etre envisageable. Ceci exclut
donc l'utilisation de tout algorithme utilisant l'insertion (le tri par
insertion par exemple), mais aussi ceux qui deplacent des
elements sans les positionner a leur place
definitive (le tri bulle par exemple). Une methode de tri sera
par exemple un tri par selection et creation d'un nouveau
fichier. L'acces au donnees devra etre optimise : on
preferera bien evidement la dichotomie
a la recherche
sequentielle, et meme on preferera une dichotomie
ponderee (avec estimation par calcul de la position probable),
puisque tout calcul sera beaucoup plus rapide qu'une lecture dans le fichier.
Un fichier a acces direct peut egalement etre
utilise pour stocker et traiter des listes, arbres ou graphes : on
utilise la methode du super-tableau : chaque element est
numerote, en fonction de sa position dans le fichier, les liens
etant ces numeros. Il faut bien garder a l'esprit qu'il ne
faut jamais stocker sur fichier un pointeur : l'adresse ou a
ete mise la valeur pointee a peu de chances d'etre
la meme a la prochaine utilisation du programme. Ils est alors
toujours necessaire de numeroter les composantes et remplacer les
pointeurs par le numero de la valeur pointee avant de faire une
sauvegarde sur fichier.
La methode souvent la plus efficace pour l'utilisation de
fichiers sequentiels est l'indexation
(elle est egalement utilisable pour les autres types de donnees,
stockees en memoire). Les composantes sont stockees dans
le fichier dans l'ordre de leur creation. On utilise alors un tableau
d'index, donnant en premiere position le numero de la
premiere composante, puis de la seconde,... L'avantage de cette
methode est que l'ajout de composantes est optimal : on rajoute la
valeur en fin de fichier, on met a jour le tableau d'index.
Tout deplacement d'une composante sera donc remplace par une
modification du tableau d'index, sans deplacement reel de la
valeur dans le fichier. En general, ce tableau peut tenir en
memoire, ce qui permet une modification rapide, en general
on prefere le sauver egalement sur support
magnetique avant de quitter le programme, ce qui evitera de le
recreer (par exemple refaire un tri) a la prochaine utilisation.
On peut egalement utiliser une liste d'index si les deplacements
sont frequents (mais alors l'acces devient sequentiel). Le
second avantage de cette methode est que l'on peut utiliser
simultanement plusieurs index : par exemple pour une liste de personnes,
on peut creer un index pour le classement alphabetique des noms,
un autre sur les villes, on accedera donc plus rapidement a tous
les champs indexes, alors que les champs non indexes devront se
satisfaire d'une recherche sequentielle, et ce sans modification dans le
fichier (un tri par nom puis par ville auraient ete
necessaires sans indexation). Par contre toute modification
necessitera la mise a jour de tous les tableaux d'index. Exemple:
La suppression, par contre, pose probleme. En
general, toujours pour eviter les decalages dans
les fichiers, on prefere marquer d'un signe distinctif les champs
supprimes (par exemple un nom non alphabetique ou vide), puis
remettre a jour les index qui ne pointeront plus sur ce champ. Le
retassage, assez long, n'est effectuee que sur ordre de l'utilisateur ou
lorsqu'il quitte le programme. On peut aussi (comme dans la methode du
super-tableau) creer une liste des champs vides, ce qui permettra d'y
acceder, plus rapidement que par une recherche sequentielle, lors
de la prochaine insertion.
Sur un fichier indexe, on peut a nouveau se permettre des
algorithmes utilisant l'insertion, puisque celle-ci n'affecte que l'index
(a acces rapide). Pour un tri par exemple, on pourra utiliser le
tri par insertion,
a condition d'optimiser la recherche de la position d'insertion (par
dichotomie ponderee par exemple), puisque celle-ci
necessite des lectures de champs dans le fichier alors que l'insertion
n'entraine que des decalages dans un tableau, d'une duree
generalement negligeable devant le temps pris par la
recherche. On peut egalement utiliser une liste d'index plutot
qu'un tableau si necessaire.