Je veux en savoir plus sur " essai structures de données ". J'ai lu des articles à leur sujet sur Wikipédia, mais je ne comprends toujours pas.
Quelle est l'utilisation la plus courante ? L'autocomplétion dans la barre d'adresse d'un navigateur web... ou ?
A la vôtre !
Un Trie (je préfère l'appeler un arbre de préfixes), pourrait être une bonne structure de données pour construire un dictionnaire efficace en mémoire avec des recherches rapides, et oui, l'autocomplétion.
Considérez-le comme une table de hachage, qui permet de consulter rapidement des paires clé-valeur (ou simplement des clés), mais contrairement à une table de hachage, il vous permet d'itérer sur les clés dans un ordre trié.
Vous trouverez les structures trie au cœur de nombreuses applications bioinformatiques (alignement de séquences d'ADN, etc.). Voir : Structures de données basées sur des triades pour l'assemblage de séquences (pdf)
Le trie est également au cœur de l'un des algorithmes de tri les plus rapides connus : Burstsort . L'implémentation consiste à construire un trie et à le parcourir en profondeur. Sa vitesse est obtenue grâce à ses propriétés d'efficacité du cache. Voir : Tri efficace, basé sur les Trie, de grands ensembles de chaînes de caractères (pdf)
Il convient de noter que Hadoop a récemment fixé un repère de tri record. Sa mise en œuvre utilise des structures trie : Code source Terasort
J'ai utilisé des tableaux modifiés dans mon Filtre Internet depuis 1995. Il est probable que la plupart des filtres Internet sur le marché utilisent quelque chose de similaire. L'avantage est que le temps nécessaire pour trouver une correspondance est lié à la longueur de la correspondance, et non au nombre d'éléments dans la structure de données. Voir aussi mon article : Arbre rapide
--jeffk++
Une autre utilisation est le Algorithme de recherche de chaînes de caractères d'Aho-Corasick qui est basé sur une trie.
Clojure L'immuable et génial de l'entreprise Carte et les types Vector sont implémentés en utilisant une trie sous les couvertures. Considérez, par exemple, l'implémentation de PersistentHashMap .
La raison pour laquelle je dis qu'ils sont "méchamment cool" est qu'ils sont immuables, ce qui offre de grands avantages pour la programmation concurrente. (Vous n'avez pas besoin de synchroniser l'accès à quelque chose qui ne peut pas changer.) En même temps, vous pouvez générer de nouvelles copies altérées d'une collection très efficacement parce qu'elles ne sont pas réellement copiées, elles partagent la structure avec la collection source.
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.
