Structures de données

Une structure de données combine une représentation et des invariants qui rendent un ensemble d’opérations efficace. Choisissez-la d’après la charge de travail, pas selon un classement générique d’« avantages » et d’« inconvénients ».

Commencer par les opérations

Besoin	Représentation typique	Point fort
Accès aléatoire par position	tableau / tableau dynamique	indexation en $O(1)$, localité
Insertion locale avec un nœud connu	liste chaînée	modification des pointeurs
Accès dernier entré, premier sorti	type abstrait pile	discipline à une extrémité
Accès premier entré, premier sorti	type abstrait file	traitement ordonné
Recherche exacte par clé	table de hachage	recherche en temps constant en espérance
Clés ordonnées et intervalles	arbre de recherche équilibré	opérations ordonnées logarithmiques
Minimum ou maximum répété	tas	mises à jour logarithmiques, accès constant à la racine
Relations arbitraires	représentation de graphe	parcours et algorithmes de chemin

Représentation et interface

Une pile ou une file est un type abstrait de données : son contrat limite l’élément qui peut être retiré. Elle peut être implémentée avec un tableau, des nœuds chaînés ou un autre conteneur. Tableau et liste chaînée décrivent plutôt l’organisation du stockage.

Questions à poser

1. Quelles opérations dominent et quels sont leurs coûts dans le pire cas ou amortis ?
2. Les références, indices ou l’ordre d’itération doivent-ils rester stables après mutation ?
3. La capacité est-elle bornée et l’allocation est-elle permise pendant l’opération ?
4. Quelle importance ont la localité du cache et le surcoût par élément ?
5. La concurrence, la persistance ou la propriété font-elles partie du contrat ?

Les coûts asymptotiques sont nécessaires mais incomplets : deux opérations en $O(1)$ peuvent différer fortement en allocation, indirection et localité.

Considérer la charge complète

Supposons qu’un programme reçoive $n$ tâches avant de les traiter dans l’ordre d’arrivée. Les ajouter en fin de tableau dynamique demande un travail total linéaire, mais supprimer sans cesse la position zéro déplace $(n-1)+(n-2)+\cdots+1$ références : un travail quadratique. Une file avec des opérations d’extrémité constantes conserve un coût total linéaire. Si les tâches sont plutôt consultées régulièrement par position numérique, le tableau dynamique peut mieux convenir. La comparaison des structures linéaires relie ces choix à des implémentations concrètes.

Le tableau oriente le choix de structures en mémoire contenant $n$ éléments ; ce n’est pas une garantie universelle. La recherche par hachage suppose une charge contrôlée et un hachage adapté, tout en payant le calcul du hachage et la comparaison des clés ; les collisions peuvent rendre le pire cas linéaire. Les bornes des arbres équilibrés comptent les comparaisons, et l’accès à la racine d’un tas suppose celui-ci non vide. Pour distinguer pire cas, espérance et amortissement, commencez par la complexité temporelle.

Source

• Open Data Structures

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.