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

Question

Il existe des structures de données qui sont très utiles mais qui sont inconnues de la plupart des programmeurs. Quelles sont-elles ?

Tout le monde connaît les listes liées, les arbres binaires et les hachages, mais qu'en est-il des Sauter les listes y Filtres Bloom par exemple. J'aimerais connaître d'autres structures de données qui ne sont pas si courantes, mais qui méritent 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 Liens de danse qui font un usage astucieux des propriétés d'une structure de données commune.

EDIT : S'il vous plaît, essayez de inclure des liens vers des pages décrivant les structures de données de manière plus détaillée. Essayez également d'ajouter un ou deux mots sur pourquoi une structure de données est cool (comme Jonas Kölker déjà souligné). Essayez également de fournir une structure de données par réponse . Cela permettra aux meilleures structures de données de se hisser au sommet sur la base de leurs seuls votes.

Answer 1

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

Answer 2

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

Pour ajouter un élément, vous le faites passer par k des fonctions de hachage qui vous donneront k dans le tableau que vous fixez ensuite à 1.

Pour vérifier si un élément fait partie de l'ensemble, calculez la formule k et vérifiez s'ils sont tous à 1.

Bien sûr, cela donne une certaine probabilité de faux positifs (selon wikipedia, elle est 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 mettre en œuvre la méthode suivante filtre bloom de comptage représenté par un tableau d'entiers et incrémenté/décrémenté.

Answer 3

Cordage : Il s'agit d'une chaîne de caractères qui permet d'effectuer des prépensions, des sous-chaînes, des insertions et des ajouts intermédiaires bon marché. Je n'en ai vraiment eu besoin qu'une seule fois, mais aucune autre structure n'aurait suffi. Les chaînes régulières et les prépends de tableaux étaient tout simplement trop chers pour ce que nous devions faire, et inverser tout était hors de question.

Answer 4

Sauter les listes sont plutôt chouettes.

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

Ils peuvent être utilisés comme une alternative aux arbres équilibrés (en utilisant un équilibrage probabiliste plutôt qu'une application stricte de l'équilibrage). Ils sont faciles à mettre en œuvre et plus rapides que, par exemple, un arbre rouge-noir. Je pense qu'ils devraient être dans la boîte à outils de tout bon programmeur.

Si vous voulez obtenir une introduction approfondie aux listes d'exclusion, voici une lien vers une vidéo de la conférence Introduction aux algorithmes du MIT.

Aussi, aquí est une applet Java qui présente visuellement les listes de saut.

Answer 5

Indices spatiaux en particulier Arbres R y Arbres KD Ils permettent de stocker efficacement des données spatiales. Ils conviennent bien aux données de coordonnées de cartes géographiques et aux algorithmes de placement et de routage VLSI, et parfois à la recherche du plus proche voisin.

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