Comment implémenter et utiliser les structures de données classiques ?
On désigne par le terme structure de données une implémentation offrant la possibilité de stocker et retrouver des données. Les implémentations qui serviront d'exemples se veulent simples, afin d'en faciliter la compréhension. Le but n'est pas de fournir l'implémentation la plus performante, que ce soit en vitesse d'exécution ou en espace mémoire occupé. De très nombreuses structures de données utilisées dans les développements professionnels sont d'ailleurs des variantes d'une, ou de plusieurs, structures simples. C'est pourquoi les points importants de chaque implémentation, formalisant les concepts impliqués dans le fonctionnement de chacune des structures, seront indiqués. Nous invitons le lecteur à prendre part à cette visite guidée afin de cerner quelle structure de données répond à quel besoin. Quelques questions pour identifier la structure appropriéeNous allons, au travers de quelques questions, approcher l'usage des différentes structures de données. Une description plus détaillée est disponible dans les articles respectifs de chacune des structures. L'ordre dans lequel les données sont ajoutées est-il important ?De nombreuses structures de données conservent l'ordre d'ajout des éléments. Dès que l'ordre dans lequel les données sont ajoutées puis retrouvées doit être préservé, les structures suivantes sont adéquates. L'accès à un élément par sa position est-il nécessaire ?Un tableau dynamique, ou même statique, permet de réaliser des accès rapides aux éléments étant donné leur positions. Il est cependant à remarquer que l'insertion d'éléments au milieu des données déjà présentes ou la suppression d'éléments existants peuvent s'avérer très coûteux en performance ! L'usage des tableaux dynamiques est très semblable à celui de n'importe quel tableau en VB. Outre les nombreux algorithmes reposant sur la manipulation de tableau, ce type de structure peut aussi servir à la construction de structures plus spécialisées, telles que les files et les piles. Les ajouts ou lectures doivent-ils toujours se faire au début, ou à la fin des données déjà présentes ?Des structures telles que les piles (le dernier élément ajouté est le premier élément retrouvé) ou les files (le premier élément ajouté est le premier élément retrouvé) sont appropriées. La pile est très souvent utilisée pour sauvegarder des contextes successifs. Un exemple simple étant le bouton undo, qui permet de revenir à un contexte précédent, où la modification n'avait pas encore été effectuée. Les files sont souvent utilisées pour permettre la communication entre deux composants ou lorsque des données doivent être traitées de manière séquentielle Est-ce que les données présentent une hiérarchie ?Certaines structures représentent de manière inhérente une hiérarchie dans les données. C'est notament le cas des arbres, et plus particulièrement des arbres binaires. Les ajouts ou suppressions sont-ils fréquents ?Lorsque l'agencement des données est souvent modifié, une liste liée, ou l'une de ses variantes, est souvent utilisée. Il est à remarquer qu'une liste doublement liée, dont les éléments sont de plus conservés dans une table de hachage, possède à la fois des propriétés de ré-agencement et d'accès rapide. C'est cette implémentation qui est à la base de l'objet Collection de Visual Basic. Le stockage offert par les listes liées présente l'avantage d'être extrêmement flexible. Lorsqu'un tableau ne possède des données utiles qu'à peu d'endroits, les listes liées permettent d'implémenter un tableau creux en réduisant efficacement l'espace mémoire occupé. En outre, ce type de structure peut servir à la construction de structures plus spécialisées, telles que les files et les piles. Est-il souhaitable que les données soient triées ?Différentes structures telles que les arbres binaires de recherche ont la propriété de contenir des données triées. C'est aussi le cas d'une variante des tableaux dynamiques, appelée SortedList, pour laquelle un algorithme de tri est appliqué lors de l'ajout des éléments. Est-ce que l'énumération des données contenues est de peu d'importance ?Plusieurs structures permettent de travailler sur les données contenues indépendamment de leur agencement. Leur faible nombre d'opérations, très spécialisées, leur permet d'atteindre de très hautes performances en comparaison de bon nombre d'autres structures. Par contre, bien qu'il soit possible de retrouver toutes les données contenues, ces structures ne sont généralement pas conçues dans cette optique. La vitesse d'exécution est-elle une facteur important ?Les tables de hachage permettent un accès extrêmement rapide aux éléments contenus. C'est l'outil idéal pour déterminer l'existence d'un mot dans un dictionnaire de plusieurs milliers d'entrées. L'espace occupé en mémoire est-il important ?Un arbre à lettres, ou trie, est une structure arborescente particulièrement appropriée pour retrouver de manière rapide la présence d'une aiguille dans une botte de foin. De plus, l'espace occupé en mémoire par cette structure de données reste faible lorsque le nombre d'éléments contenus augmente suffisamment. Ceci en fait donc un précieux outil pour rechercher l'ensemble des mots connus contenus dans un texte. D'autres structures de données, d'autres présentationsDe nombreuses autres structures de données, telles que les tas binaires (heap), différents arbres balancés, graphes, etc. n'ont pas été présentées. Il est aussi possible de présenter très différemment les structures de données existantes. Sont elles ou non arborescentes ? Quelle est l'occupation mémoire engendrée par l'utilisation de telle ou telle structure ? Si tout ne peut être abordé en un seul article, les références ci-dessous apporteront certainement d'autres informations utiles. Aller plus loin |
Top