Structures de données avancées en pratique

Question

Depuis dix ans que je programme, je peux compter sur une main le nombre de structures de données que j'ai utilisées : tableaux, listes chaînées (je mets dans le même sac les piles et les files d'attente) et dictionnaires. Ce n'est pas vraiment surprenant étant donné que presque toutes les applications que j'ai écrites tombent dans la catégorie des formulaires sur les données / CRUD.

Je n'ai jamais eu besoin d'utiliser un arbre rouge-noir, une liste de saut, une file d'attente à double extrémité, une liste liée circulairement, une file d'attente prioritaire, des tas, des graphes ou l'une des dizaines de structures de données exotiques qui ont fait l'objet de recherches au cours des 50 dernières années. J'ai l'impression de manquer quelque chose.

Il s'agit d'une question ouverte, mais où ces structures de données "exotiques" sont-elles utilisées dans la pratique ? Quelqu'un a-t-il une expérience réelle de l'utilisation de ces structures de données pour résoudre un problème particulier ?

Answer 1

Quelques exemples. Ils sont vagues car il s'agissait de travaux pour les employeurs :

• A amas pour obtenir les N premiers résultats d'une recherche de type Google. (En partant des candidats dans un index, on les parcourt tous linéairement, en les passant au crible d'un mini-hélice de taille maximale N). Ceci était pour un prototype de recherche d'images.

• Filtres Bloom réduire la taille de certaines données relatives à ce que des millions d'utilisateurs ont vu à une quantité qui peut tenir dans les serveurs existants (tout devait être en RAM pour la vitesse) ; la conception originale aurait nécessité de nombreux nouveaux serveurs juste pour cette base de données.

• A représentation d'un réseau triangulaire divisé par deux la taille d'un tableau symétrique dense pour un moteur de recommandation (RAM à nouveau pour la même raison).

• Les utilisateurs devaient être regroupés en fonction de certaines associations ; union-find a rendu ça facile, rapide et exact au lieu de lent, bidouillé et approximatif.

• Une application permettant de choisir les sites de vente au détail en fonction du temps de trajet des habitants du quartier. Le plus court chemin de Dijkstra avec des files d'attente prioritaires. D'autres travaux SIG ont tiré parti de quadtrees y Morton les indices.

Il est utile de savoir ce qui se passe au pays des structures de données : "des semaines au laboratoire peuvent vous faire gagner des heures à la bibliothèque". Le cas du bloom-filter n'était intéressant qu'à cause de l'échelle : si le problème s'était posé dans une startup plutôt que chez Yahoo, j'aurais utilisé une bonne vieille table de hachage. Les autres exemples me semblent raisonnables partout (même si de nos jours, il est moins probable que vous les codiez vous-même).

Answer 2

Arbres B sont dans des bases de données.

Arbres R sont destinés aux recherches géographiques (par exemple, si j'ai 10000 formes, chacune avec une boîte de délimitation, dispersées dans un plan 2-D, lesquelles de ces formes croisent une boîte de délimitation arbitraire B ?)

deques du formulaire dans le C++ STL sont des vecteurs croissants (plus efficaces en mémoire que les listes chaînées, et en temps constant pour "peeker" des éléments arbitraires au milieu). Autant que je m'en souvienne, je n'ai jamais utilisé le deque dans toute son étendue (insertion/suppression à partir des deux extrémités) mais il est suffisamment général pour que vous puissiez l'utiliser comme une pile (insertion/suppression à partir d'une extrémité) ou une file d'attente (insertion à une extrémité, suppression à partir de l'autre) et avoir également un accès performant pour visualiser des éléments arbitraires au milieu.

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

Les files d'attente prioritaires sont utilisées, entre autres, pour l'ordonnancement (voici une page web qui traite brièvement de l'application) ; les tas sont généralement utilisés pour les mettre en œuvre. J'ai également constaté que le heapsort (pour moi du moins) est le plus facile à comprendre et à mettre en œuvre parmi les tris O(n log n).

Answer 3

Ils sont souvent utilisés en coulisses dans les bibliothèques. Par exemple, une structure de données de dictionnaire ordonné (c'est-à-dire un tableau associatif qui permet une traversée triée par clés) a autant de chances d'être implémentée en utilisant un fichier arbre rouge-noir.

De nombreuses structures de données ( arbres d'alignement me viennent à l'esprit) sont intéressants pour leur comportement optimal dans certaines circonstances ( localité temporelle de référence dans le cas des arbres d'évitement), ils sont donc principalement pertinents pour une utilisation 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.

Prenons l'exemple du tri :

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

• le principal avantage d'un amas trier est que cela peut être fait en in situ avec un minimum d'interventions stockage intermédiaire minimal, ce qui en fait une bonne pour une utilisation dans des mémoire. Bien qu'elle soit plus lente en moyenne (bien que toujours n log(n)), il ne souffre pas de la mauvaise performance dans le pire des cas de quicksort.

• Un troisième exemple est un fusionner trier ce qui peut être fait séquentiellement, ce qui en fait la meilleure choix pour trier des ensembles de données beaucoup plus grands 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 les résultats intermédiaires.

Answer 4

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

Je sais que j'ai une expérience similaire à la vôtre. Au niveau d'abstraction actuel de la plupart des développements logiciels. Les dictionnaires et les listes sont les principales structures de données que nous utilisons.

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

Answer 5

J'utilise constamment des tampons en anneau et des files d'attente circulaires dans mes travaux d'intégration pour gérer les interruptions (par exemple, les ports série).

Les structures arborescentes sont très utilisées en infographie.

Si vous utilisez les structures de données STL map ou set, alors vous utilisez probablement un arbre rouge-noir sans même le savoir !