Quelles sont les structures de données et les algorithmes moins connus que l'on devrait connaître?

Question

Récemment, j'ai découvert la structure de données SkipList. Cela m'a vraiment aidé à résoudre un problème autrement difficile à résoudre. Je luttais pour le résoudre en utilisant l'arbre binaire équilibré, mais il est devenu très complexe car l'arbre doit toujours être équilibré et je voulais connaître l'existence non seulement d'une valeur particulière, mais de valeurs dans une certaine gamme. SkipList m'a aidé à résoudre ce problème efficacement. Je me demande quelles sont les autres structures de données dont j'ai besoin de connaître? Je sais à propos de - Array, liste, pile, file d'attente, liste liée, hashtable, arbre et ses différentes formes comme B-tree, Trie etc. Aimeriez-vous savoir si vous trouvez une autre structure de données/concept intéressant et utile dans un cycle de développement régulier.

Answer 1

Vous n'avez pas mentionné les graphiques qui sont très puissants et si vous ne les connaissez pas, vous devriez absolument les lire. Recherchez l'algorithme de Dijkstra et l'algorithme de recherche A *, ainsi que la première recherche en profondeur et la première recherche en profondeur.

Vous avez également omis les tas, qui sont souvent utilisés comme structure sous-jacente pour une file d'attente prioritaire. Les tas binaires sont les plus simples, mais vous pouvez aussi regarder dans les tas min-max-médians, les tas binomiaux (fusions rapides) et les tas de Fibonacci (clé de décroissance rapide - utile pour certains algorithmes de graphes).

D'autres structures de données intéressantes incluent des essais de Patricia qui sont des tentatives d'espace-efficaces (claveté sur des sous-chaînes au lieu des caractères), des arbres d'écart, qui sont équilibrés et peuvent être programmés pour être persistants. Consultez également les filtres Bloom, qui est une structure de données probabiliste qui vous permet de déterminer si un élément est membre d'un ensemble. Il peut avoir des faux positifs mais pas des faux négatifs et est efficace dans l'espace/temps. Enfin, vous pouvez utiliser la route fonctionnelle et examiner les structures de données immuables et persistantes. Beaucoup d'entre elles ne sont que des versions fonctionnelles des structures de données que vous connaissez déjà. Si cela vous intéresse, je vous recommande de consulter les Datastructures purement fonctionnelles d'Okasaki.

Answer 2

Vous avez à la fois "List" et "Linked List", et il n'est pas du tout clair quelle différence (le cas échéant) vous voulez entre les deux. Quoi qu'il en soit, une structure évidente que vous avez ignorée est le tas (que vous pourriez classer comme un type d'arbre, mais c'est assez incertain au mieux). En fin de compte, les arbres sont un sous-ensemble de graphiques, donc si vous n'avez pas étudié les graphiques (en général) c'est probablement une zone à explorer.

Je tiens à préciser que rien de tout cela n'est particulièrement "récent" - ils sont tous connus depuis des décennies. La plupart de ces structures vraiment générales sont connues depuis longtemps. Plus récemment, ceux qui ont été découverts ont tendance à se rapporter à des domaines plus spécifiques.