Quelles sont les structures de données les moins connues mais utiles?

Il existe des structures de données qui sont vraiment utiles mais inconnues de la plupart des programmeurs. Quels sont-ils?

Tout le monde connaît les listes liées, les arbres binaires et les hachages, mais qu'en est-il des listes de saut et des filtres Bloom par exemple. J'aimerais en savoir plus sur les structures de données qui ne sont pas si courantes, mais qui méritent d'être connues car elles reposent sur de bonnes idées et enrichissent la boîte à outils d'un programmeur.

PS: Je m'intéresse également à des techniques comme les liens de danse qui utilisent intelligemment les propriétés d'une structure de données commune.

EDIT : Veuillez essayer d' inclure des liens vers des pages décrivant les structures de données plus en détail. Essayez également d'ajouter quelques mots sur les raisons pour lesquelles une structure de données est cool (comme Jonas Kölker l'a déjà souligné). Essayez également de fournir une structure de données par réponse . Cela permettra aux meilleures structures de données de flotter vers le haut en fonction de leurs seuls votes.

Les essais , également connus sous le nom d'arbres préfixes ou d'arbres à bits critiques , existent depuis plus de 40 ans mais sont encore relativement inconnus. Une utilisation très intéressante des essais est décrite dans " TRASH - Une structure de données dynamique de tri-LC et de hachage ", qui combine un trie avec une fonction de hachage.

Filtre Bloom : tableau de bits de m bits, initialement tous mis à 0.

Pour ajouter un élément, vous l'exécutez via k fonctions de hachage qui vous donneront k indices dans le tableau que vous définissez ensuite sur 1.

Pour vérifier si un élément est dans l'ensemble, calculez les k indices et vérifiez s'ils sont tous définis sur 1.

Bien sûr, cela donne une certaine probabilité de faux positifs (selon wikipedia, il s'agit d'environ 0,61 ^ (m / n) où n est le nombre d'éléments insérés). Les faux négatifs ne sont pas possibles.

La suppression d'un élément est impossible, mais vous pouvez implémenter un filtre de floraison de comptage , représenté par un tableau d'ints et une augmentation / diminution.

Corde : c'est une chaîne qui permet des ajouts, des sous-chaînes, des insertions et des ajouts bon marché. Je ne l'ai vraiment utilisé qu'une seule fois, mais aucune autre structure n'aurait suffi. Les pré-ajouts de chaînes et de tableaux réguliers étaient bien trop chers pour ce que nous devions faire, et inverser tout était hors de question.

Les listes de sauts sont assez soignées.

Wikipedia
Une liste de saut est une structure de données probabiliste, basée sur plusieurs listes liées triées parallèles, avec une efficacité comparable à un arbre de recherche binaire (journal des commandes n temps moyen pour la plupart des opérations).

Ils peuvent être utilisés comme une alternative aux arbres équilibrés (en utilisant l'équilibrage probaliste plutôt que l'application stricte de l'équilibrage). Ils sont faciles à mettre en œuvre et plus rapides que, disons, un arbre rouge-noir. Je pense qu'ils devraient être dans tous les bons ensembles d'outils de programmeurs.

Si vous souhaitez obtenir une introduction approfondie aux listes à sauter, voici un lien vers une vidéo de la présentation du MIT sur les algorithmes.

En outre, voici une applet Java illustrant visuellement les sauts de listes.

Indices spatiale , en particulier R arbres et KD-arbres , stocker des données spatiales de manière efficace. Ils sont bons pour les données de coordonnées de carte géographique et les algorithmes de localisation et d'itinéraire VLSI, et parfois pour la recherche du plus proche voisin.

Les tableaux de bits stockent les bits individuels de manière compacte et permettent des opérations de bits rapides.

Fermetures à glissière - dérivés de structures de données qui modifient la structure pour avoir une notion naturelle de «curseur» - emplacement actuel. Celles-ci sont vraiment utiles car elles garantissent que les indices ne peuvent pas être hors limites - utilisés, par exemple dans le gestionnaire de fenêtres xmonad pour suivre quelle fenêtre a été focalisée.

Étonnamment, vous pouvez les dériver en appliquant des techniques de calcul au type de la structure de données d'origine!

Voici quelques-uns:

• Le suffixe essaie. Utile pour presque tous les types de recherche de chaînes (http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). Voir aussi tableaux de suffixes; ils ne sont pas aussi rapides que les suffixes, mais beaucoup plus petits.

• Évasez les arbres (comme mentionné ci-dessus). La raison pour laquelle ils sont cool est triple:

  • Ils sont petits: vous n'avez besoin que des pointeurs gauche et droit comme vous le faites dans n'importe quel arbre binaire (aucune information de couleur ou de taille de nœud ne doit être stockée)
  • Ils sont (comparativement) très faciles à mettre en œuvre
  • Ils offrent une complexité amortie optimale pour toute une série de "critères de mesure" (le temps de recherche log n étant celui que tout le monde connaît). Voirhttp://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

• Arborescences de recherche ordonnées par segments: vous stockez un tas de paires (clés, prio) dans une arborescence, de sorte qu'il s'agit d'une arborescence de recherche par rapport aux clés, et ordonnées par segments en fonction des priorités. On peut montrer qu'un tel arbre a une forme unique (et il n'est pas toujours entièrement emballé de haut en bas). Avec des priorités aléatoires, il vous donne le temps de recherche O (log n) prévu, IIRC.

• Une niche est celle des listes d'adjacence pour les graphes planaires non orientés avec des requêtes de voisin O (1). Il ne s'agit pas tant d'une structure de données que d'un moyen particulier d'organiser une structure de données existante. Voici comment faire: chaque graphe planaire a un nœud avec un degré au plus 6. Choisissez un tel nœud, mettez ses voisins dans sa liste de voisins, supprimez-le du graphique et répétez jusqu'à ce que le graphique soit vide. Lorsqu'on leur donne une paire (u, v), recherchez u dans la liste des voisins de v et pour v dans la liste des voisins de u. Les deux ont une taille maximale de 6, c'est donc O (1).

Selon l'algorithme ci-dessus, si u et v sont voisins, vous n'aurez pas à la fois u dans la liste de v et v dans la liste de u. Si vous en avez besoin, ajoutez simplement les voisins manquants de chaque nœud à la liste de voisins de ce nœud, mais stockez la quantité de la liste de voisins que vous devez parcourir pour une recherche rapide.

Je pense que les alternatives sans verrou aux structures de données standard, c'est-à-dire la file d'attente, la pile et la liste sans verrou, sont très négligées.
Ils sont de plus en plus pertinents car la simultanéité devient une priorité plus élevée et est un objectif beaucoup plus admirable que d'utiliser des mutex ou des verrous pour gérer les lectures / écritures simultanées.

Voici quelques liens
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Liens vers le PDF]
http://www.boyet.com/Articles/LockfreeStack.html

Le blog de Mike Acton (souvent provocateur) contient d'excellents articles sur la conception et les approches sans verrou

Je pense que Disjoint Set est assez astucieux pour les cas où vous devez diviser un groupe d'éléments en ensembles distincts et appartenir à une requête. Une bonne mise en œuvre des opérations Union et Find se traduit par des coûts amortis qui sont effectivement constants (inverse de la fonction d'Ackermnan, si je me souviens bien de ma classe de structures de données).

Tas de Fibonacci

Ils sont utilisés dans certains des algorithmes connus les plus rapides (asymptotiquement) pour de nombreux problèmes liés aux graphiques, tels que le problème du chemin le plus court. L'algorithme de Dijkstra s'exécute en temps O (E log V) avec des tas binaires standard; l'utilisation des tas de Fibonacci améliore cela en O (E + V log V), ce qui est une énorme accélération pour les graphiques denses. Malheureusement, cependant, ils ont un facteur constant élevé, ce qui les rend souvent peu pratiques dans la pratique.

Toute personne ayant une expérience en rendu 3D doit être familiarisée avec les arbres BSP . Généralement, c'est la méthode en structurant une scène 3D pour être gérable pour un rendu connaissant les coordonnées et le relèvement de la caméra.

Le partitionnement d'espace binaire (BSP) est une méthode pour subdiviser récursivement un espace en ensembles convexes par des hyperplans. Cette subdivision donne lieu à une représentation de la scène au moyen d'une structure de données arborescente appelée arbre BSP.

En d'autres termes, il s'agit d'une méthode de décomposition de polygones de forme complexe en ensembles convexes, ou de plus petits polygones composés entièrement d'angles non réflexes (angles inférieurs à 180 °). Pour une description plus générale du partitionnement d'espace, voir Partitionnement d'espace.

A l'origine, cette approche a été proposée en infographie 3D pour augmenter l'efficacité de rendu. Certaines autres applications incluent la réalisation d'opérations géométriques avec des formes (géométrie solide constructive) en CAO, la détection de collision dans la robotique et les jeux informatiques 3D, et d'autres applications informatiques qui impliquent la manipulation de scènes spatiales complexes.

Arbres de Huffman - utilisés pour la compression.

Jetez un œil à Finger Trees , surtout si vous êtes fan des structures de données purement fonctionnelles mentionnées précédemment . Ils sont une représentation fonctionnelle de séquences persistantes soutenant l'accès aux extrémités en temps constant amorti, et la concaténation et la division en temps logarithmique de la taille de la plus petite pièce.

Selon l'article d'origine :

Nos arbres fonctionnels à 2-3 doigts sont un exemple d'une technique de conception générale introduite par Okasaki (1998), appelée ralentissement récursif implicite . Nous avons déjà noté que ces arbres sont une extension de sa structure implicite deque, remplaçant les paires par 2-3 nœuds pour fournir la flexibilité requise pour une concaténation et un fractionnement efficaces.

Un arbre de doigt peut être paramétré avec un monoïde , et l'utilisation de différents monoïdes entraînera des comportements différents pour l'arbre. Cela permet à Finger Trees de simuler d'autres structures de données.

Tampon circulaire ou en anneau - utilisé pour le streaming, entre autres.

Je suis surpris que personne n'ait mentionné les arbres Merkle (c'est-à-dire les arbres de hachage ).

Utilisé dans de nombreux cas (programmes P2P, signatures numériques) où vous souhaitez vérifier le hachage d'un fichier entier lorsque vous ne disposez que d'une partie du fichier.

<zvrba> Arbres de Van Emde-Boas

Je pense qu'il serait utile de savoir pourquoi ils sont cool. En général, la question «pourquoi» est la plus importante à poser;)

Ma réponse est qu'ils vous donnent des dictionnaires O (log log n) avec des clés {1..n}, indépendamment du nombre de clés utilisées. Tout comme la division répétée de moitié vous donne O (log n), la sqrting répétée vous donne O (log log n), ce qui se produit dans l'arborescence vEB.

Que diriez-vous des arbres splay ?

On pense également aux structures de données purement fonctionnelles de Chris Okasaki .

Une variante intéressante de la table de hachage est appelée Cuckoo Hashing . Il utilise plusieurs fonctions de hachage au lieu d'une seule afin de gérer les collisions de hachage. Les collisions sont résolues en supprimant l'ancien objet de l'emplacement spécifié par le hachage principal et en le déplaçant vers un emplacement spécifié par une autre fonction de hachage. Cuckoo Hashing permet une utilisation plus efficace de l'espace mémoire car vous pouvez augmenter votre facteur de charge jusqu'à 91% avec seulement 3 fonctions de hachage et toujours avoir un bon temps d'accès.

Un segment min-max est une variante d'un segment qui implémente une file d'attente prioritaire à double extrémité. Il y parvient par une simple modification de la propriété du tas: Un arbre est dit être ordonné min-max si chaque élément sur les niveaux pairs (impairs) est moins (supérieur) que tous les enfants et petits-enfants. Les niveaux sont numérotés à partir de 1.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

J'aime les infrastructures de données Cache Oblivious . L'idée de base est de disposer un arbre en blocs récursivement plus petits afin que les caches de nombreuses tailles différentes tirent parti des blocs qui s'y adaptent facilement. Cela conduit à une utilisation efficace de la mise en cache sur tout, du cache L1 dans la RAM aux gros morceaux de données lus sur le disque sans avoir besoin de connaître les spécificités de la taille de l'une de ces couches de mise en cache.

Arbres rouges-noirs penchés à gauche . Une implémentation considérablement simplifiée des arbres rouge-noir par Robert Sedgewick publiée en 2008 (~ la moitié des lignes de code à implémenter). Si vous avez déjà eu du mal à vous concentrer sur la mise en œuvre d'un arbre rouge-noir, lisez cette variante.

Très similaire (sinon identique) à Andersson Trees.

File d'attente de vol de travail

Structure de données sans verrouillage pour diviser le travail de manière égale entre plusieurs threads Mise en œuvre d'une file d'attente de vol de travail en C / C ++?

Tas obliquité bootstrap binomiale par Gerth Stölting Brodal et Chris Okasaki:

Malgré leur nom long, ils fournissent des opérations de tas asymptotiquement optimales, même dans un paramètre de fonction.

• O(1)taille, union , insert, minimum
• O(log n) deleteMin

Notez que l'union prend O(1)plus de O(log n)temps que les tas les plus connus qui sont couramment couverts dans les manuels de structure de données, tels que les tas de gauche . Et contrairement aux tas de Fibonacci , ces asymptotiques sont dans le pire des cas, plutôt qu'amorties, même si elles sont utilisées de manière persistante!

Il existe plusieurs implémentations dans Haskell.

Ils ont été dérivés conjointement par Brodal et Okasaki, après que Brodal est venu avec un tas impératif avec les mêmes asymptotiques.

• Kd-Trees , structure de données spatiales utilisée (entre autres) dans le lancer de rayons en temps réel, a l'inconvénient que les triangles qui se croisent intersectent les différents espaces doivent être coupés. En général, les BVH sont plus rapides car ils sont plus légers.
• MX-CIF Quadtrees , stockez des boîtes englobantes au lieu de jeux de points arbitraires en combinant un quadtree régulier avec un arbre binaire sur les bords des quads.
• HAMT , carte de hachage hiérarchique avec des temps d'accès qui dépassent généralement O (1) les cartes de hachage en raison des constantes impliquées.
• Index inversé , bien connu dans les cercles des moteurs de recherche, car il est utilisé pour la récupération rapide de documents associés à différents termes de recherche.

La plupart, sinon la totalité, sont documentées dans le dictionnaire d'algorithmes et de structures de données du NIST

Arbres à billes. Tout simplement parce qu'ils font rire les gens.

Un arbre à billes est une structure de données qui indexe des points dans un espace métrique. Voici un article sur leur construction. Ils sont souvent utilisés pour trouver les voisins les plus proches d'un point ou pour accélérer les k-moyennes.

Pas vraiment une structure de données; plus d'un moyen d'optimiser les tableaux alloués dynamiquement, mais les tampons d'espace utilisés dans Emacs sont plutôt sympas.

Arbre de Fenwick. C'est une structure de données pour compter la somme de tous les éléments d'un vecteur, entre deux sous-indices donnés i et j. La solution triviale, précalculer la somme depuis le début ne permet pas de mettre à jour un élément (vous devez faire un travail O (n) pour suivre).

Fenwick Trees vous permet de mettre à jour et d'interroger dans O (log n), et comment cela fonctionne est vraiment cool et simple. C'est vraiment bien expliqué dans l'article original de Fenwick, disponible gratuitement ici:

http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf

Son père, l'arbre RQM est également très cool: il vous permet de conserver des informations sur l'élément minimum entre deux index du vecteur, et il fonctionne également dans la mise à jour et la requête O (log n). J'aime enseigner d'abord le RQM puis le Fenwick Tree.

Arbres de Van Emde-Boas . J'en ai même une implémentation C ++ , jusqu'à 2 ^ 20 entiers.

Les ensembles imbriqués sont agréables pour représenter les arbres dans les bases de données relationnelles et exécuter des requêtes dessus. Par exemple, ActiveRecord (ORM par défaut de Ruby on Rails) est livré avec un plugin de jeu imbriqué très simple , ce qui rend le travail avec les arbres trivial.

C'est assez spécifique au domaine, mais la structure de données à demi-bord est assez soignée. Il fournit un moyen d'itérer sur les maillages polygonaux (faces et arêtes), ce qui est très utile en infographie et en géométrie de calcul.