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


Certaines structures de données sont vraiment utiles mais sont inconnues de la plupart des programmeurs. Lesquels sont-ils?

Tout le monde connaît les listes liées, les arbres binaires et les hachages, mais qu'en est-il Sauter les listes et Filtres de Bloom par exemple. Je voudrais connaître plus de structures de données qui ne sont pas si communes, mais qui valent la peine d'être connues car elles s'appuient sur de bonnes idées et enrichissent la boîte à outils d'un programmeur.

PS: Je suis également intéressé par des techniques comme Liens de danse qui font une utilisation intelligente des propriétés d'une structure de données commune.

MODIFIER: S'il vous plaît essayer de inclure des liens aux pages décrivant les structures de données plus en détail. En outre, essayez d'ajouter quelques mots sur Pourquoi une structure de données est cool (comme Jonas Kölker déjà souligné). Aussi, essayez de fournir une structure de données par réponse. Cela permettra aux meilleures structures de données de flotter au sommet en fonction de leurs votes seuls.


797


origine


Réponses:


Essaie, également connu sous le nom préfixe-arbres ou arbres crit-bit, existent depuis plus de 40 ans mais sont encore relativement inconnus. Une utilisation très cool des essais est décrite dans "TRASH - Une structure dynamique de données LC-trie et hash", qui combine un trie avec une fonction de hachage.


271



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

Pour ajouter un élément, vous le lancez k fonctions de hachage qui vous donnera k indices dans le tableau que vous avez ensuite mis à 1.

Pour vérifier si un élément est dans l'ensemble, calculez le k indices et vérifiez s'ils sont tous mis à 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.

Retrait d'un élément est impossible, mais vous pouvez mettre en œuvre compter le bloom filter, représenté par array of ints et increment / décrément.


231



Corde: C'est une chaîne qui permet de faire des prépots, des sous-chaînes, des insertions intermédiaires et des ajouts bon marché. Je n'en ai vraiment eu l'usage qu'une seule fois, mais aucune autre structure n'aurait suffi. Les coûts habituels des chaînes et des tableaux étaient tout simplement trop élevés pour ce que nous devions faire, et il était hors de question de tout renverser.


140



Sauter les listes sont assez soignés.

Wikipédia
  Une liste de sauts est une structure de données probabiliste, basée sur plusieurs listes parallèles et triées, avec une efficacité comparable à celle d'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 à implémenter et plus rapides que l'arbre rouge-noir. Je pense qu'ils devraient être dans chaque boîte à outils de bons programmeurs.

Si vous voulez avoir une introduction détaillée aux listes de sauts, voici un lien vers une vidéo de l'introduction aux algorithmes du MIT leur expliquent.

Aussi, ici est une applet Java démontrant visuellement les listes de sauts.


128



Indices spatiaux, en particulier R-trees et KD-arbres, stocker des données spatiales efficacement. Ils sont bons pour les données de coordonnées de carte géographique et les algorithmes de localisation et de routage VLSI, et parfois pour la recherche par les plus proches voisins.

Bit Arrays stocker des bits individuels de manière compacte et permettre des opérations de bits rapides.


92



Zippers - des dérivées 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 limites - utilisé, par exemple. dans le Gestionnaire de fenêtres xmonad pour suivre quelle fenêtre a mis l'accent.

Étonnamment, vous pouvez les dériver par appliquer des techniques de calcul au type de la structure de données originale!


87



Voici quelques-uns:

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

  • Arbres Splay (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 de nœud ou de taille n'a besoin d'ê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 du journal étant celui que tout le monde connaît). Voir http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • Arborescence de recherche ordonnée en tas: vous stockez un groupe de paires (clé, prio) dans un arbre, de sorte qu'il s'agit d'un arbre de recherche par rapport aux clés, et ordonné en 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é-et-à-la-gauche). Avec des priorités aléatoires, il vous donne le temps de recherche O (log n) attendu, IIRC.

  • Un créneau est celui des listes d'adjacence pour les graphes planaires non orientés avec O (1) requêtes voisines. Ce n'est pas tant une structure de données qu'une façon particulière d'organiser une structure de données existante. Voici comment vous le faites: chaque graphe planaire a un noeud de degré au maximum 6. Choisissez un tel noeud, placez ses voisins dans sa liste de voisins, supprimez-le du graphe et recurcissez jusqu'à ce que le graphe soit vide. Lorsque vous obtenez une paire (u, v), recherchez la liste des voisins de u in v et la liste des voisins de v in u. Les deux ont une taille d'au plus 6, donc c'est O (1).

Par l'algorithme ci-dessus, si u et v sont voisins, vous n'aurez pas à la fois la liste de u dans v et la liste de v dans u. Si vous en avez besoin, ajoutez simplement les voisins manquants de chaque nœud à la liste des voisins de ce nœud, mais stockez la liste de la liste des voisins dont vous avez besoin pour rechercher rapidement.


69



Je pense que les alternatives sans verrou aux structures de données standard, telles que la file d'attente sans verrou, la pile et la liste, sont largement ignorées.
Ils sont de plus en plus pertinents car la concurrence devient une priorité plus élevée et est un objectif beaucoup plus admirable que l'utilisation de Mutex ou de 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 PDF]
http://www.boyet.com/Articles/LockfreeStack.html 

Mike Acton's (souvent provocateur) blog a d'excellents articles sur la conception et les approches sans verrou


65



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


55