Structures de données avancées dans la pratique

Les arbres B sont dans les bases de données.

R-trees sont pour les recherches géographiques (par exemple, si j'ai 10000 formes chacune avec une boîte englobante dispersée autour d'un plan 2D, laquelle de ces formes croise une boîte englobante arbitraire B?)

Les Deques de la forme dans le C++ STL sont des vecteurs cultivables (plus économes en mémoire que les listes chaînées, et à temps constant pour "jeter un coup d'œil" aux éléments arbitraires au milieu). Aussi loin que je me souvienne, je n'ai jamais utilisé le deque à son pleine étendue (insérer/supprimer des deux extrémités) mais il est assez général que vous pouvez l'utiliser comme une pile (insérer/supprimer d'une extrémité) ou une file d'attente (insérer à une extrémité, supprimer de l'autre) et avoir également un accès haute performance pour afficher des éléments arbitraires au milieu.

Je viens de finir de lire Génériques et collections Java the la partie "génériques" me fait mal à la tête, mais la partie collections était utile et ils soulignent certaines des différences entre les listes de saut et les arbres (les deux peuvent implémenter des cartes / ensembles): les listes de saut vous donnent une itération en temps constant intégrée d'un élément à l'autre (les arbres sont O(log n) ) et sont beaucoup plus simples pour implémenter des algorithmes sans verrouillage dans des situations multithread.

Sont utilisées entre autres pour la planification (voici une page Web qui discute brièvement de l'application); les tas sont généralement utilisés pour les implémenter. J'ai également trouvé que le heapsort (pour moi au moins) est le plus facile des tries O(n log n) à comprendre et de mettre en œuvre.

Ils sont souvent utilisés dans les coulisses des bibliothèques. Par exemple, une structure de données de dictionnaire ordonnée (c'est-à-dire un tableau associatif qui indique une traversée triée par clés) est aussi susceptible de ne pas être implémentée à l'aide d'un arbre rouge-noir.

De nombreuses structures de données (splay trees viennent à l'esprit) sont intéressantes pour leur comportement optimal dans certaines circonstances (localité temporelle de référence dans le cas des splay trees), elles sont donc principalement pertinentes pour utilisez dans ces cas. Dans la plupart des cas, le véritable avantage d'une connaissance pratique de ces structures de données est de pouvoir les utiliser dans les bonnes circonstances avec une compréhension raisonnable de leur comportement.

Prenez le tri, par exemple:

• Dans la plupart des cas quicksort ou un quicksort modifié qui tombe à une autre méthode lorsque le les segments individuels deviennent assez petits est généralement le tri le plus rapide algorithme pour la plupart des fins. Cependant, quicksort a tendance à montrer comportement sous optimal sur données presque triées.

• Le principal avantage d'un tas sort est que cela peut être fait dans situ avec intermédiaire minimal stockage, ce qui le rend assez bon pour une utilisation dans la mémoire contrainte système. Alors qu'il est plus lent en moyenne (bien que toujours n log(n)), il ne souffre pas de la mauvaise performance du pire des cas de quicksort.

• Un troisième exemple est un fusion trier , ce qui peut être fait séquentiel, c'est la meilleure choix pour trier les ensembles de données beaucoup plus grand que votre mémoire principale. Un autre nom pour cela est le "tri externe", ce qui signifie que vous pouvez trier en utilisant un stockage externe (disque ou bande) pour des résultats intermédiaires.

Cela dépend du niveau d'abstraction auquel vous travaillez.

Je sais que j'ai la même expérience que vous. Au niveau actuel d'abstraction de la plupart des développements logiciels. Dictionnaire et la Liste sont les principales structures de données que nous utilisons.

Je pense que si vous regardez le code de niveau inférieur, vous verrez plus de structures de données "exotiques".

J'utilise constamment des tampons en anneau/des files d'attente circulaires dans le travail intégré pour entretenir les interruptions (par exemple, les ports série).

Les structures arborescentes sont fortement utilisées en infographie.

Si vous utilisez une carte STL ou définissez des structures de données, vous utilisez probablement un arbre rouge-noir sans même le savoir!

Je pense que vous voyez des structures de données sophistiquées utilisées la plupart des algorithmes de niveau supérieur. L'exemple principal qui me vient à l'esprit est A* qui utilise un graphique et une File d'attente prioritaire implémentée par un tas.

Dans finance, vous devez utiliser un arbre pour calculer la valeur d'un instrument qui dépend de nombreuses autres valeurs dynamiques. Les feuilles de calcul ont un arbre de dépendances similaire, et les compilateurs créent un arbre de syntaxe abstraite avant de traduire en code machine.

Des tas de Fibonacci sont utilisés pour les implémentations efficaces de l'algorithme de Dijkstra.

Oui, parfois. Le problème que je vois c'est qu'un certain nombre de gens, bien qu'ils les connaissent, ils ne savent pas comment les appliquer. La plupart des gens reviennent aux tableaux aux listes liées,etc. Ils feront le travail dans la plupart des cas en tant que structure de données plus avancée (parfois, vous devez vraiment "lancer" en place), ils sont juste moins efficaces. Les gens ont tendance à faire ce qui est plus facile pour eux, mais ce n'est pas nécessairement la meilleure façon de faire quelque chose. Je ne peux pas leur reprocher, je suis sûr que je le fais aussi, mais c'est pourquoi vous ne voyez pas beaucoup de concepts "avancés" dans la programmation.

Je viens de trouver une utilisation pour les graphiques en posant une question sur stackoverflow:)

J'ai utilisé des listes chaînées circulaires pour implémenter des files d'attente (en C) que je vais parcourir pour toujours, c'est-à-dire une file d'attente de connexion réseau.

Mais je trouve que lorsque j'utilise des langages de niveau supérieur, je ne me dérange pas d'implémenter des files d'attente de cette manière, car je peux développer et réduire dynamiquement une liste sans trop m'en soucier. Bien sûr, il y a un prix de performance pour cela, parce que j'ai moins de contrôle sur le moment où l'allocation de mémoire se produit, mais c'est l'un des prix que nous payons pour pouvoir avoir des listes très flexibles.

Vous aurez tendance à voir des structures de données plus compliquées lorsque cela est dicté par les besoins du code. Habituellement, je vais voir cela lorsque vous avez affaire à du code plus complexe à des niveaux inférieurs, c'est-à-dire dans le système d'exploitation principal, en écrivant des parties fondamentales d'une bibliothèque de classes (implémentation de string, array, etc.), en écrivant du code extrêmement performant ou multithread, etc. L'autre endroit, je pense qu'ils jouent un rôle important dans la mise en œuvre des algorithmes spécifiques, la recherche, l'échantillonnage, l'analyse statistique, les algorithmes d'optimisation, etc. sont souvent écrits avec des structures de données particulières à l'esprit.

J'utilise souvent des ensembles, des collections triées (gardez toujours leurs éléments dans l'ordre trié et supportez l'insertion rapide d'éléments) et des listes paresseuses.

Les arbres équilibrés (rouge-noir, etc.) sont généralement utilisés dans l'implémentation d'un type de données abstrait.

Il n'y a qu'un nombre relativement faible de types de données abstraites, tels que

• liste
• carte
• carte ordonnée
• carte multiple
• plusieurs cartes ordonnées
• file d'attente prioritaire (qui ressemble beaucoup à une carte multi ordonnée)

De même, un ensemble ressemble beaucoup à une carte, mais vous n'avez pas besoin des valeurs, seulement des clés.

J'ai trouvé la plupart des ceux-ci sont utiles de temps en temps; une file d'attente prioritaire est une structure de données très utile et a des applications dans toutes sortes d'algorithmes (par exemple, la planification, la recherche de chemin, etc.).

Vous avez dit "Dictionnaire", vous vouliez probablement dire une carte ou une carte ordonnée.

Certaines cartes ne sont pas ordonnées (généralement implémentées sous forme de hachage) - c'est un sous-ensemble utile d'une carte ordonnée.

J'ai utilisé une liste circulaire pour la mise en cache.

Un modèle de classe C++ fournit une interface pour obtenir des objets (Cache<Obj, Len>). Plusieurs instatinations de celui-ci renvoient différents types d '"écrans" comme dans différentes vues d'une interface graphique. Dans les coulisses, si l'écran demandé n'est pas disponible, il est créé (opération coûteuse) et poussé à la tête du tampon d'anneau, poussant le plus ancien (déchargeant ses textures, etc.).

Ainsi un compromis est atteint entre toujours lire un tas de fichiers image à partir du disque dur, et simplement charger toutes les images dans la RAM et les garder pour toujours. Le compromis est contrôlé par la longueur des différents tampons.