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

il y a certaines structures de données autour qui sont vraiment utiles, mais sont inconnues de la plupart des programmeurs. Qui sont-ils?

tout le monde connaît les listes liées, les arbres binaires et les hachures, mais qu'en est-il de Skip lists et Bloom filters par exemple. J'aimerais en savoir plus sur les structures de données qui ne sont pas si courantes, mais qui valent la peine d'être connues parce qu'elles reposent sur de grandes idées et enrichissent la boîte à outils d'un programmeur.

PS: je suis également intéressé par des techniques comme Dancing links qui font une utilisation Intelligente des propriétés d'une structure de données commune.

EDIT : S'il vous plaît essayer de inclure des liens à des pages décrivant les structures de données plus en détail. Aussi, essayer d'ajouter un couple de mots sur pourquoi une structure de données est cool (comme Jonas Kölker déjà souligner.) Aussi, essayer de fournir une structure de données par réponse . Cela permettra aux meilleures structures de données de flotter vers le haut sur la base de leurs seuls votes.

797
demandé sur f3lix 2009-02-01 14:12:25
la source

30 ответов

Tries , aussi connu sous le nom de prefix-trees ou crits-bit trees , existent depuis plus de 40 ans mais sont encore relativement inconnus. Une utilisation très cool de tries est décrite dans " TRASH - une structure dynamique de données LC-trie et de hachage ", qui combine un trie avec une fonction de hachage.

271
répondu David Phillips 2010-10-05 19:34:55
la source

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

pour ajouter un article que vous exécutez à travers k fonctions de hachage qui vous donnera k indices dans le tableau que vous mettez alors à 1.

pour vérifier si un article est dans l'ensemble, calculez les indices k et vérifiez s'ils sont tous réglés à 1.

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

supprimer un élément est impossible, mais vous pouvez mettre en œuvre counting bloom filter , représenté par un tableau d'ints et incrément/décrément.

231
répondu albwq 2009-02-18 23:01:36
la source

corde : c'est une corde qui permet des prépends, des substrats, des insertions intermédiaires et des appends bon marché. Je ne l'ai utilisé qu'une fois, mais aucune autre structure n'aurait suffi. La préparation des cordes et des tableaux était beaucoup trop chère pour ce que nous avions à faire, et inverser tout était hors de question.

140
répondu Patrick 2009-02-19 22:09:10
la source

Skip lists sont très soigné.

Wikipedia

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

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

si vous voulez obtenir une introduction en profondeur à skip-lists voici un lien vers une vidéo de L'Introduction de MIT aux algorithmes conférence sur eux.

aussi, ici est une applet Java démontrant des listes de saut visuellement.

128
répondu Simucal 2009-02-22 07:15:46
la source

les "Indices spatiaux , en particulier R-trees et KD-trees , stockent efficacement les données spatiales. Ils sont bons pour les coordonnées géographiques et les algorithmes de localisation et de route VLSI, et parfois pour la recherche du voisin le plus proche.

tableaux de bits stocker les bits individuels de façon compacte et permettre des opérations de bits rapides.

92
répondu Yuval F 2009-02-01 15:23:44
la source

Zippers - dérivés de structures de données qui modifient la structure pour avoir une notion naturelle de 'curseur' -- emplacement actuel. Ceux-ci sont vraiment utiles car ils garantissent que les indices ne peuvent pas être hors limite -- utilisé, par exemple dans le xmonad window manager pour suivre quelle fenêtre a mis l'accent.

Étonnamment, vous pouvez les déduire par appliquer des techniques de calcul à la type de l'original de la structure de données!

87
répondu Don Stewart 2010-07-23 07:01:31
la source

En voici quelques-uns:

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

  • "151900920 Splay arbres (comme mentionné ci-dessus). La raison pour laquelle ils sont frais est triple:

    • ils sont petits: vous avez seulement besoin des pointeurs gauche et droite comme vous le faites dans n'importe quel arbre binaire (aucun noeud-couleur ou information de taille doit être stocké)
    • 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). Voir http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • arbres de recherche ordonnés par tas: vous stockez un tas de (clé, prio) paires dans un arbre, tel qu'il s'agit d'un arbre de recherche par rapport aux clés, et par ordre de tas par rapport aux priorités. On peut montrer qu'un tel arbre a une forme unique (et il n'est pas toujours complètement emballé à gauche). Avec des priorités aléatoires, il vous donne prévu o (log n) Le temps de recherche, list et pour V dans la liste des voisins de U. Les deux ont la taille AU PLUS 6, donc c'est O(1).

par l'algorithme ci-dessus, si u et v sont voisins, vous n'aurez pas u dans la liste de v et v dans la liste de U. Si vous avez besoin de ceci, ajoutez simplement les voisins manquants de chaque noeud à la liste des voisins de ce noeud, mais stockez combien de la liste des voisins vous avez besoin de regarder à travers pour la recherche rapide.

69
répondu Jonas Kölker 2009-02-01 15:12:30
la source

I think lock-free alternatives to standard data structures I. la file d'attente, la pile et la liste sont négligées.

Ils sont de plus en plus pertinents car la concurrence devient une priorité plus élevée et sont beaucoup plus admirable objectif que d'utiliser des Mutex ou des serrures pour gérer la lecture/écriture 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 au 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 serrure

65
répondu zebrabox 2010-05-26 21:39:14
la source

je pense Disjoints Ensemble est assez chouette pour les cas où vous avez besoin de diviser un tas d'éléments dans des ensembles distincts de requête et de l'adhésion. Une bonne mise en œuvre de L'Union et les opérations de Find entraînent des coûts amortis qui sont effectivement constants (inverse de la fonction D'Ackermnan, si je me souviens de ma classe de structures de données correctement).

55
répondu Dana 2009-02-18 23:17:50
la source

les tas de Fibonacci

ils sont utilisés dans certains des algorithmes les plus rapides connus (asymptotiquement) pour un grand nombre de problèmes liés au graphique, tels que le problème de chemin le plus court. L'algorithme de Dijkstra fonctionne dans le temps O(E log V) avec des tas binaires standard; en utilisant des tas Fibonacci améliore cela à O(E + V log V), qui est une énorme accélération pour les graphiques denses. Malheureusement, ils ont un facteur constant élevé, ce qui les rend souvent impraticables dans la pratique.

52
répondu Adam Rosenfield 2011-06-19 21:22:57
la source

toute personne ayant de l'expérience dans le rendu 3D devrait connaître BSP trees . En général, c'est la méthode en structurant une scène 3D pour être gérable pour un rendu connaissant les coordonnées et le roulement de la caméra.

partitionnement de l'espace binaire (BSP) est un méthode pour subdiviser de façon récursive un espace en ensembles convexes par hyperplanes. Cette subdivision donne lieu à un représentation de la scène par le biais d'un arbre de données structure connue comme une BSP tree.

en d'autres termes, c'est une méthode de cassant en forme complexe polygones en ensembles convexes, ou plus petits polygones constitués entièrement de angles non-réflexes (angles inférieurs à 180°). Pour une description plus générale de partitionnement de l'Espace, voir Espace partitionner.

à l'Origine, cette approche a été proposée dans l'infographie 3D pour augmenter le rendu de l'efficacité. Certains autres application comprennent la réalisation d' opérations géométriques avec formes (géométrie solide constructive) en CAO, détection de collision en robotique et 3D les jeux d'ordinateur, et d'autres ordinateur les demandes qui impliquent le traitement de spatiale complexe scènes.

44
répondu spoulson 2009-02-18 23:26:32
la source

Huffman arbres - utilisé pour la compression.

43
répondu Lurker Indeed 2009-02-22 07:47:47
la source

regardez Finger Trees , surtout si vous êtes un fan des déjà mentionnés structures de données purement fonctionnelles. C'est une représentation fonctionnelle de séquences persistantes supportant l'accès aux extrémités en temps constant amorti, et la concaténation et la division en temps logarithmique dans la taille de la plus petite pièce.

Que par l'article original :

nos arbres à deux ou trois doigts fonctionnels 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 deque implicite, remplaçant les paires par 2-3 noeuds pour fournir la flexibilité requise pour la concaténation efficace et le fendage.

un arbre à doigts peut être paramétré avec un monoid , et l'utilisation de différents monoïdes se traduira par des comportements différents pour l'arbre. Cela permet aux arbres à doigts de simuler d'autres structures de données.

38
répondu huitseeker 2017-05-23 15:26:36
la source

circular or ring buffer - utilisé pour le streaming, entre autres choses.

34
répondu cdonner 2009-03-17 21:30:42
la source

je suis surpris que personne n'ait mentionné les arbres de Merkle (i.e. Hachage Arbres ).

utilisé dans de nombreux cas (programmes P2P, signatures numériques) où vous voulez vérifier le hachage d'un fichier entier lorsque vous n'avez qu'une partie du fichier à votre disposition.

33
répondu BlueRaja - Danny Pflughoeft 2010-01-28 23:03:29
la source

< zvrba> Van Emde-boas trees

je pense qu'il serait utile de savoir pourquoi ils sont cool. En général, la question "pourquoi" est le plus important à demander ;)

ma réponse est qu'ils vous donnent des dictionnaires O(log n) Avec {1..n} clés, indépendamment de combien de clés sont en cours d'utilisation. Tout comme la réduction de moitié répétée vous donne O (log n), La sqrting répétée vous donne O (log n), Ce Qui Est ce ça se passe dans le vEB tree.

32
répondu Jonas Kölker 2009-02-01 16:27:26
la source

Que Diriez-vous de splay trees ?

aussi, purely functional data structures de Chris Okasaki viennent à l'esprit.

31
répondu starblue 2010-01-17 13:24:57
la source

une variante intéressante de la table de hachage est appelé coucou de hachage . Il utilise plusieurs fonctions de hachage au lieu de seulement 1 pour traiter les collisions de hachage. Les Collisions sont résolues en enlevant l'ancien objet de l'emplacement spécifié par le hachage primaire et en le déplaçant vers un emplacement spécifié par une autre fonction de hachage. Coucou Hashing permet une utilisation plus efficace de l'espace mémoire car vous pouvez augmenter votre facteur de charge jusqu'à 91% avec seulement 3 hash fonctions et ont encore un bon temps d'accès.

29
répondu A. Levy 2009-05-11 01:56:05
la source

a min-max heap est une variante d'un tas qui implémente une file d'attente de priorité double extrémité. Il y parvient par un simple changement à la propriété heap: un arbre est dit min-max ordonné si chaque élément sur les niveaux pairs (impairs) sont moins (plus grands) 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

27
répondu marcog 2011-01-15 15:18:07
la source

j'aime Cache Inconscient structures de données . L'idée de base est de disposer un arbre dans des blocs plus petits de façon récursive afin que les caches de différentes tailles puissent profiter des blocs qui s'y intègrent facilement. Cela conduit à une utilisation efficace de la mise en cache pour tout, du cache L1 en RAM aux gros morceaux de données lus sur le disque sans avoir besoin de connaître les détails des tailles de n'importe laquelle de ces couches de mise en cache.

26
répondu btilly 2011-03-25 01:20:26
la source

Gauche Penchant Arbres Rouge-Noir . De manière significative une mise en oeuvre simplifiée des arbres rouge-noir par Robert Sedgewick publié en 2008 (environ la moitié de la lignes de code à mettre en œuvre). Si vous avez déjà eu du mal à vous concentrer sur la mise en œuvre d'un arbre rouge-noir, lisez à propos de cette variante.

très similaire (sinon identique) aux Andersson.

23
répondu Lucas 2010-05-23 21:21:19
la source

File D'Attente Pour Le Vol Au Travail

structure de données sans serrure pour diviser le travail de façon égale entre plusieurs fils mise en Œuvre d'un travail de voler de la file d'attente en C/C++?

22
répondu Marko Tintor 2017-05-23 14:55:03
la source

bootstrapped skew-binomial heaps 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 cadre de fonction.

  • O(1) taille de, union , d'insertion, minimum
  • O(log n) deleteMin

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

Il y a multiple implémentations en Haskell.

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

19
répondu Edward KMETT 2010-07-23 10:15:19
la source
  • "KD-Trees , structure de données spatiales utilisée (entre autres) dans le Raytracing en temps réel, présente l'inconvénient que les triangles qui croisent les différents espaces doivent être coupés. En général, les BVH sont plus rapides parce qu'ils sont plus légers.
  • MX-CIF Quadtrees , stockez des boîtes limitantes au lieu d'ensembles de points arbitraires en combinant un quadtree régulier avec un arbre binaire sur les bords des quads.
  • HAMT , hiérarchique hachage carte avec les temps d'accès qui sont généralement supérieures à O(1) hachage-cartes en raison de l'constantes concernées.
  • index inversé , assez connu dans les cercles des moteurs de recherche, parce qu'il est utilisé pour la récupération rapide de documents associés à différents termes de recherche.

la plupart, sinon la totalité, de ceux-ci sont documentés sur le NIST Dictionary of Algorithmes et structures de données

18
répondu Jasper Bekkers 2009-02-18 23:16:22
la source

Le Bal Des Arbres. Juste 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 à un point ou l'accélération k-moyens.

18
répondu 2 revsanon 2010-07-23 06:28:24
la source

N'est pas vraiment une structure de données; il s'agit plutôt d'une façon d'optimiser les tableaux alloués dynamiquement, mais les gap buffers utilisés dans Emacs sont plutôt cool.

17
répondu kerkeslager 2010-05-24 01:52:47
la source

Fenwick Tree. Il s'agit d'une structure de données permettant de compter la somme de tous les éléments d'un vecteur, entre deux sous-Indexes i et J. La solution triviale, en précalculant la somme depuis le début ne permet pas de mettre à jour un élément (vous devez faire un travail O(n) pour suivre).

les arbres Fenwick vous permettent de mettre à jour et d'interroger dans O(log n), et comment cela fonctionne est vraiment cool et simple. C'est très bien expliqué dans le papier 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 aussi très cool: il vous permet de garder des informations sur l'élément minimum entre deux index du vecteur, et il fonctionne aussi dans o(log n) update et query. J'aime enseigner d'abord le RQM et ensuite le Fenwick Tree.

16
répondu eordano 2010-07-23 07:45:43
la source

Van Emde-boas trees . J'ai même un c++ implémentation de celui-ci, pour jusqu'à 2^20 entiers.

14
répondu zvrba 2009-02-01 16:06:37
la source

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 sur eux. Par exemple , ActiveRecord (L'ORM par défaut de Ruby on Rails) est livré avec un très simple emboîté plugin set , ce qui rend le travail avec les arbres trivial.

13
répondu esad 2010-05-23 04:02:56
la source

c'est assez spécifique au domaine, mais " la structure de données de demi-bord est assez soignée. Il fournit un moyen d'itérer au-dessus des mailles de polygone (faces et bords) qui est très utile dans l'infographie et la géométrie computationnelle.

12
répondu mpen 2010-05-23 11:31:25
la source