MISE EN ŒUVRE

Question

Existe-t-il des implémentations de trie en C / C ++ efficaces en termes de rapidité et de cache efficace? Je sais ce qu'est un essai, mais je ne veux pas réinventer la roue, la mettre en œuvre moi-même.

Answer 1

si vous recherchez une implémentation ANSI C, vous pouvez la "voler" à FreeBSD. Le fichier que vous recherchez s'appelle radix.c . Il est utilisé pour gérer les données de routage dans le noyau.

Answer 2

Je me rends compte que la question a été sur le point d'implémentations, mais pour la référence...

Avant de sauter sur Judy vous devriez avoir lu "Une Comparaison des Performances de Judy pour les Tables de Hachage". Puis googler le titre devrait vous donner une durée de vie de discussion et rebutals à lire.

Explicitement cache-conscient trie que je connaisse est le HAT-trie.

Ce sont les deux (dans mon esprit) des structures de données complexes. La complexité est mauvais. Si je ont été, après un trie aujourd'hui, j'aimerais recherchez un burst-trie.

Answer 3

J'ai eu de la chance avec libTrie . Ce n'est peut-être pas spécifiquement optimisé pour le cache, mais les performances ont toujours été bonnes pour mes applications.

Answer 4

Tableaux Judy : Tableaux dynamiques clairsemés ordonnés très rapides et efficaces en termes de mémoire pour les bits, les entiers et les chaînes. Les tableaux Judy sont plus rapides et utilisent plus efficacement la mémoire que n’importe quel arbre de recherche binaire (y compris les arbres avl et red-black-trees).

Answer 5

Références,

• Un article sur l' implémentation Double-Array Trie (inclut une implémentation C )
• TRASH - Structure dynamique de données de tri-hachage et de hachage - (référence PDF 2006 décrivant une tri-trie dynamique utilisée dans le noyau Linux pour implémenter la recherche d'adresses dans la table de routage IP