7:Structures de données
Dans la plupart des cours de programmation, le chapitre sur les structures de données commence par traiter des enregistrements et tableaux. De notre point de vue “écologique”, nous faisons une grande différence entre ces structure figées, “minérales” et les structures “végétales”, basées sur les pointeurs et donc capables de croître et de changer de forme.La notion de pointeur peut effrayer le programmeur “haut-niveau” qui travaille avec des langages comme VisualBasic ou Java desquels les pointeurs ont délibérément été exclus. Il n’en reste pas moins que de manière interne, les structures de données mises à disposition par ces langages utilisent les pointeurs de la même manière que celles que l’on peut écrire soi-même en C++ par exemple.
Choisir la bonne plante
La bonne structure de données est celle qui permet d’utiliser les algorithmes avec la plus faible complexité pour résoudre les problèmes posés. Voilà, ce n’est pas plus compliqué que ça. Le tout est de connaître sur le bout du pouce le coût des algorithmes de base correspondant aux structures courantes, résumées dans le tableau suivant, et de bien réfléchir dans les autres cas.
| Accès au i ème élément | Recherche | Insertion (à la position i) | Tri | Redimensionnement | |
|---|---|---|---|---|---|
| Vecteur | O(1) | O(N/2) | O(N-i) | O(N.log N) | O(N) |
| Liste | O(i) | O(N/2) | O(i) | O(N.log N) | O(1) |
| Liste Triée | O(i) | O(log N) | O(log N) | 0 | O(1) |
| Arbre binaire | O(log N) | O(log N) | O(log N) | O(1) .. O(N.log N) | O(1) |
| Association | O(N/2) | O(log N) | O(log N) | O(1) | |
| Table hachée | O(1) | O(1) .. O(N) | O(N) |
Nous n’allons pas détailler toutes les structures de données classiques (liste, pile, arbre, etc.) et encore moins traiter des algorithmes souvent liés au traitement de ces structures, il existe de nombreux ouvrages sur ce sujet. Il est plus intéressant de voir comment définir la structure de données la plus adaptée à un problème précis. Mais avant cela, nous allons quand même parler de quelques structures qui offrent des avantages décisifs du point de vue des performances.
Vecteurs
Le vecteur est un bambou virtuel : il est composé d’un nombre déterminé d’emplacements contigus en mémoire et contenant chacun une donnée. Le mot important est « contigu », car il conditionne à la fois le plus grand avantage et le gros inconvénient du vecteur :
- L’accès au i-ème élément est très rapide car il suffit d’ajouter à l’adresse du 1er élément i-1 fois la taille d’une donnée. C’est d’ailleurs pour économiser le « -1 » que la plupart des langages numérotent les vecteurs à partir de 0.
- Le vecteur n’a qu’un avantage par rapport au tableau minéral : il peut pousser, et doit donc pouvoir être déplacé en mémoire pour rester contigu, ce qui implique de copier les N données qu’il contient. Rien de bien méchant en apparence, mais si un programmeur avait la mauvaise idée d’ajouter un à un 1000 éléments dans un vecteur, il y aurait 1000 réallocations du vecteur, et 500′000 copies d’éléments ! Il existe bien sûr des astuces pour éviter ceci :
- ne stocker que des types prédéfinis dans le vecteur. Stocker des vecteurs sur des données plus grandes, ça facilite énormément la copie.
- allouer plus de place que nécessaire au vecteur, et utiliser un nombre pour compter le nombre d’éléments réellement utilisés. On peut alors ne réallouer que lorsque la place est totalement occupée, et libérer une partie de la mémoire lorsque la taille diminue au dessous d’un seuil. Ce mécanisme peut être totalement automatisé et devenir invisible pour l’utilisateur, ce qui a du bon, mais peut aussi endormir sa conscience écologique, comme on le verra au paragraphe « Stringologie »
Comme on l’a vu au paragraphe « La Pile tombe… à pic ! », un vecteur, ou même un tableau, permet de réaliser une pile de façon très efficace. D’autres structures comme les « tampons circulaires » fort utiles en télécommunication peuvent aussi être réalisés avec un vecteur plutôt qu’à base de pointeurs et bénéficier ainsi à la fois d’une vitesse d’exécution et d’une fiabilité améliorée.
Tables de hachage
Les tables de hachage sont rarement abordées dans les cours ou les livres de programmation car il est difficile d’en parler de manière générale. En effet, ce ne sont que des vecteurs dotés de fonctions d’indexation qui sont en principe spécifiques à l’application considérée. Et qu’est-ce donc qu’une fonction d’indexation ? C’est un algorithme de complexité O(1) qui prend en entrée une donnée « clé » servant d’indice et fournit en sortie l’indice numérique de la donnée dans un tableau ou vecteur.
S’il est par exemple facile de trouver la fonction d’indexation permettant d’indicer un vecteur avec une date (jour+31*mois+372*année, parce que 12*31=372), il est nettement plus difficile de trouver une fonction d’indexation prenant par exemple une chaîne de caractères en entrée, mais on tentera cependant de le faire au paragraphe « Jardinage et jeux de lettres ».
Une bonne fonction d’indexage doit :
- être « dense », c’est-à-dire pouvoir remplir un vecteur de taille N avec le maximum de données. Par exemple, notre fonction d’indexation pour dates a une densité de 365,25/372, soit 98%, ce qui n’est pas mal du tout.
- être « scalable » c’est-à-dire pouvoir s’adapter à des vecteurs de diverses tailles. Ceci est crucial pour pouvoir gérer des tables de taille élastique. En effet, lorsqu’on ajoute des éléments à la table, il arrive immanquablement que la fonction d’indexage tente de placer une donnée à une place déjà occupée. On peut alors gérer cette « collision » en agrandissant le vecteur pour lui permettre de stocker plus de données. Mais il faut que la fonction d’indexation soit modifiée en conséquence, et utilisée pour replacer les données existantes à leur nouvelle position dans le vecteur agrandi.
C’est la difficulté de trouver des fonctions d’indexage remplissant ces deux critères, surtout le second, qui limite l’utilisation pratique des tables de hachage. Mais l’avantage décisif de la recherche en O(1) et de l’insertion en O(1) vaut souvent la peine de se creuser la tête.
Une alternative au problème de la « scalabilité » est d’accepter les collisions en stockant plusieurs données dans l’entrée du vecteur correspondant à la clé. Nous allons illustrer cette technique au paragraphe suivant.
Jardinage et jeux de lettres
Il ne faut d’autre part pas hésiter à combiner plusieurs structures de données pour sculpter une solution efficace. Voici pour commencer un petit problème de jeu de lettres qui démontrera l’importance de concevoir des structures de données adaptées au problème:
“trouver un mot de 8 lettres dans un dictionnaire de la langue française, tel qu’un mot de 7 lettres obtenu en enlevant une lettre figure aussi dans le dictionnaire, et qu’un mot de 6 lettres obtenu en enlevant une lettre de plus figure également dans le dictionnaire etc jusqu’à une seule lettre.
L’algorithme “force brute” consiste à chercher les n mots de 8 lettres du dictionnaire (O(N)), puis pour chacun d’eux, enlever successivement chaque lettre et vérifier s’il est présent dans le dictionnaire (O(N.log N) pour liste triée), et recommencer s’il y est. La complexité est environ O(N+n.100.N.log N). Le facteur 100 est une estimation du nombre de recherches dans le dictionnaire pour chaque mot avant d’arriver à une impasse. Avec typiquement N=30′000 et n=5′000, on se retrouve avec 240 milliards de comparaisons de chaînes de caractères à effectuer si l’on veut trouver toutes les solutions. Compter une petite heure.
On pourrait se satisfaire de ceci et se demander pourquoi passer des heures à programmer une solution plus futée. Et bien, si on est capable de retrouver rapidement les mots qui ne se distinguent d’un autre que par une seule lettre, ou deux ou trois, on obtient un correcteur d’orthographe rapide et efficace. Mais pour une telle application, la complexité mentionnée ci-dessus serait inacceptable.
Comment accélérer très sérieusement la recherche de mots “semblables” a un autre dans un dictionnaire? Quelques idées:
- grouper les mots par tailles. Si on cherche un mot de 6 lettres, on ne le cherchera que parmi ceux-là.
- construire une “signature” du mot sous la forme d’un ensemble de 26 bits indiquant quelles lettres sont présentes dans le mot, et grouper les mots ayant la même signature (donc composés des mêmes lettres) dans une liste. 26 bits, c’est moins que 32, donc très pratique à manipuler par le processeur pour des opérations logiques. Mais c’est trop pour être utilisé comme clé dans une table de hachage, qui aurait dans les 64 millions d’entrées.
- Si on parvenait à réduire la taille de la signature à 16 bits, on pourrait l’utiliser comme clé pour un accès quasiment instantané dans une table de 65′536 entrées, ce qui est un peu supérieur au nombre de mots figurant dans un dictionnaire standard. On devrait donc arriver à faire une fonction de hachage relativement dense. Une possibilité est de n’utiliser que les 16 bits correspondant aux lettres les plus fréquentes dans la langue du dictionnaire, soit en français ESN…
Pour la séparation données/algorithmes !
Avant de faire le contraire au Chapitre 8 : Objets, argumentons en faveur d’une séparation nette entre la botanique des structures de données, et la génétique du code. Certes, comme nous l’avons vu dans ce chapitre, les deux sont liés : une structure de donnée sans algorithme d’insertion ou de recherche n’est que du bois mort. Mais d’autres algorithmes sont très indépendants de la structure. Un tri « quick-sort » fonctionne de manière identique sur un vecteur de nombres, une liste de villes ou un dictionnaire de mots.