795 votes

Ce sont les moins connus mais utile des structures de données?

Il y a quelques structures de données autour de qui sont vraiment utiles mais qui sont inconnus de la plupart des programmeurs. Qui sont-ils?

Tout le monde connaît les listes chaînées, arbres binaires, et les tables de hachage, mais qu' Ignorer les listes et filtres de Bloom par exemple. Je voudrais savoir plus de structures de données qui ne sont pas communs, mais valent la peine de savoir, parce qu'ils comptent sur de grandes idées et enrichir un programmeur de la boîte à outils.

PS: je suis aussi intéressé par des techniques comme la Danse des liens qui rendent l'utilisation intelligente des propriétés d'une structure commune de données.

EDIT: S'il vous plaît essayez d' inclure des liens vers des pages décrivant les structures de données plus en détail. Aussi, essayez d'ajouter quelques mots sur le pourquoi d'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 va permettre d'améliorer la qualité des structures de données à flotter vers le haut en raison de leurs votes seul.

271voto

David Phillips Points 3413

Essaie, aussi connu comme préfixe des-arbres ou des crit bits arbres, ont existé pendant plus de 40 ans, mais sont encore relativement inconnu. Très cool l'utilisation de la tente est décrit dans la "CORBEILLE - UNE dynamique LC-trie de hachage et de la structure de données", qui combine un trie avec une fonction de hachage.

231voto

albwq Points 1215

La floraison de filtre: tableau de Bits de m bits, tous mis à 0.

Pour ajouter un élément de l'exécuter par le biais de k fonctions de hachage qui vous donnera k indices dans le tableau qui vous puis la valeur 1.

Pour vérifier si un élément est dans l'ensemble, calcul de la k indices et vérifier s'ils sont tous à 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). Le nombre de faux négatifs ne sont pas possibles.

La suppression d'un élément, c'est impossible, mais vous pouvez mettre en œuvre comptage filtre de bloom, représentée par un tableau d'entiers et d'incrément/décrément.

140voto

Patrick Points 20392

Corde: C'est une chaîne qui permet pour pas cher ajoute, sous-chaînes, au moyen d'insertions et ajoute. J'ai vraiment seulement eu pour une fois, mais aucune autre structure aurait suffi. Régulièrement des chaînes et des tableaux ajoute étaient juste trop cher pour ce que nous devions faire, et le renversement de tout ce dont il était hors de question.

128voto

Simucal Points 34961

Skip lists sont très soigné.

Wikipédia
Un saut de liste est un probabiliste de la structure de données, basée sur de multiples parallèles, triés listes liées, avec une efficacité comparable à un arbre de recherche binaire (de l'ordre de log n temps moyen pour la plupart des opérations).

Ils peuvent être utilisés comme une alternative à l'équilibre des arbres (à l'aide de probalistic équilibrage plutôt qu'une stricte application de la loi de l'équilibre). Ils sont faciles à mettre en œuvre et plus rapide que de dire, d'un rouge-l'arbre noir. Je pense qu'ils devraient être dans tous les bons programmeurs toolchest.

Si vous voulez vous faire une introduction approfondie à la skip-lists ici est un lien vers une vidéo du MIT Introduction aux Algorithmes conférence sur eux.

Aussi, ici, est une applet Java démontrant Skip Lists visuellement.

92voto

Yuval F Points 15248

Indices spatiaux, en particulier la R-arbres et les KD-trees, de stocker des données spatiales de manière efficace. Ils sont bons pour la carte géographique de coordonner les données et VLSI, de placement et de routage algorithmes, et parfois pour le plus proche voisin de recherche.

Peu de Tableaux stocker des bits de façon compacte et permettre rapide des opérations sur les bits.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X