Les essais sont-ils toujours une bonne idée sur les architectures modernes?

Question

L'une de mes structures de données préférées à l'université était le Trie. C'est une excellente structure de données pour conserver un grand nombre de chaînes si les préfixes sont partagés. Les recherches sont également intéressantes, puisqu'elles sont faites à O (| longueur |) de la chaîne indépendamment du nombre de chaînes présentes dans l'ensemble. En comparaison, un arbre équilibré serait O (log N) dans le nombre d'éléments définis, plus tout ce que vous payez pour les comparaisons. Une table de hachage impliquerait le calcul de hachage, la comparaison, etc.

Il est donc surprenant pour moi que there is no Trie implementation in the standard library of most languages. La seule raison pour laquelle je suis arrivé à la conclusion était la possibilité que les coûts d'accès à la mémoire le rendent trop cher. Plutôt que d'enquêter sur les emplacements O (log N) si vous effectuez une recherche arborescente, vous ne faites pas O (| longueur |) emplacements différents, avec toutes les conséquences. Si les cordes sont longues, cela pourrait être trop lourd.

Donc je me demande: combien est ce que je viens de décrire une préoccupation? Que faites-vous lorsque vous avez besoin de stocker un grand ensemble ou une carte de chaînes?

Answer 1

Je n'avais pas pensé à cela comme un sujet de préoccupation avant, mais maintenant que vous le mentionnez, il y a des moments où une implémentation standard de Trie pourrait être utile. D'un autre côté, autant que je sache, les Tries sont utilisés par Python et Perl et d'autres langages à cordes que j'utilise maintenant.

Dernière vérification, il y a longtemps, le code du noyau BSD utilisait Tries (Patricia Tries) dans le code pour sélectionner la meilleure interface pour l'envoi de paquets. Ressemble à Wikipedia has some info.

Answer 2

Vous pouvez simplement créer deux exemples d'applications et voir lequel fonctionne le mieux. L'accès à la mémoire est bon marché en supposant que vous n'avez pas de défaut de page. Alors c'est très cher. Pour le développement d'applications client, il est presque toujours préférable de traiter que d'accéder à la mémoire pour cette raison. Les processeurs modernes sont ridiculement rapides, mais les échecs de cache font encore mal.

Answer 3

J'ai effectué quelques tests de performance en C# avec un Trie et un Dictionary (une table de hachage fortement typée). J'ai trouvé que le dictionnaire était 5-10 fois plus rapide que le Trie. Peut-être que ma mise en œuvre de la Trie pourrait être optimisée un peu, mais à peine suffisante pour être beaucoup plus rapide que (ou peut-être même aussi rapide que) le dictionnaire. La méthode ContainsKey dans le dictionnaire est proche d'une opération O (1) (selon la qualité de l'algorithme de hachage), il n'est donc pas facile de faire une collection qui bat aussi longtemps que l'algorithme de hachage est raisonnablement rapide .

Avec un IEqualityComparer personnalisé, vous pouvez utiliser la plupart des éléments comme clé dans un dictionnaire, ce qui le rend plutôt flexible. Un Trie est un peu plus limité dans ce que vous pouvez utiliser comme clé, ce qui limite quelque peu l'utilité.