Bestiaire des structures de données

Oct. 22, 2018, 5:59 p.m. Edited on May 18, 2021, 11:05 p.m.

Structures communes

Structure Commentaire
liste suite d'éléments
ensemble se comporte comme un sac d'éléments (sans ordre). On peut tester si un élément donné est dans le sac
dictionnaire / tableau associatif permet d'associer un élément à un autre. Se comporte aussi comme un ensemble
graphe points reliées par des liens
arbre préfixe forme d'arbre où chaque nœud représente un préfixe
tas structure où le minimum (ou maximum, au choix) est immédiatement disponible (base commune des files de priorité, utiles notamment à l'algo de Dijkstra)

Structures avancées

Structure Commentaire
Arbre d'intervalles permet de stocker des intervalles et tester leur intersection
Union-find permet de déterminer incrémentalement le partitionnement d'un ensemble (composantes connectées incrémentales, Kruskal)
Arbre bicolore arbre équilibré
B Tree cousin de l'arbre bicolore regroupant, éléments dans le même nœud
Quad / Oct Tree permet d'indexer des éléments dans l'espace
Arbre de Merkle permet de vérifier l'intégrité / identifier de très gros arbres (Git)

Bestioles ésotériques

Structure Commentaire
Filtre de Bloom permet de tester la probable présence d'un élément dans un set (utilisés et dans l'éditeur de lien dynamique GNU)
HyperLogLog permet d'estimer le nombre d'éléments uniques dans un flux (dans redis)
Treap ensemble ordonné, hybride entre tas et arbre (usages: ça et ça)
Locality sensitive hashing recherche de similarités dans des espaces à haute dimension
Skip list liste à l'accès aléatoire « rapide » (presque utile)
VList hybride vecteur / liste
Arbre de recherche ternaire arbre préfixe avec bonne utilisation mémoire
Arbre de Van Emde Boas tableau associatif (dictionnaire) ordonné
Arbre préfixe compressé par niveau meilleure utilisation mémoire que les arbres préfixes normaux (tables de routage)
Corde Permet d'éditer facilement du texte
Structure de Dietz Permet de maintenir efficacement un ordre absolu
Arbre d'ondelettes Compression de chaines

~

Vous en voulez plus ?

Quelle structure est la plus efficace pour votre problème ? http://bigocheatsheet.com/

Oct. 22, 2018, 10:01 p.m. Edited on Oct. 22, 2018, 10:12 p.m.

Mon but initial était plus de montrer des trucs ésotériques :p

J'ai honnêtement jamais sérieusement considéré utiliser plus de trois des éléments de cette liste. J'en rajoute des plus communes

EDIT: c'est fait

Reply to the thread

You have to register or log in to post messages.