Complexité de l'opération de recherche sur un nedtrie (bitwise trie)

Question

J'ai récemment entendu parler de nedtries et j'ai décidé d'essayer de les implémenter, mais quelque chose me gêne sur la complexité de leur opération de recherche; Je ne supporte pas pourquoi ils sont supposés être si rapides. D'après ce que j'ai compris, la complexité attendue de leur opération de recherche devrait être O (m/2) avec m la taille de la clé en bits. Si on le compare à la complexité de l'opération de recherche dans un arbre binaire traditionnel, vous obtenez: log2 (n)> = m/2

Soit de la clé soit 32bits longue: log2 (n)> = 16 < => n> = 65536

Les nédatures doivent donc être plus rapides que les arbres binaires à partir de 65536 éléments. Cependant, l'auteur affirme qu'ils sont toujours plus rapides que l'arbre binaire, donc soit mon hypothèse sur leur complexité est fausse ou les calculs effectués à chaque étape de la recherche sont beaucoup plus rapides dans une nedtrie.

Alors, qu'en est-il?

Answer 1

Si vous avez des arbres plus petits, vous pouvez utiliser des petites clés!

Answer 2

(Note Je suis l'auteur de nedtries). Je pense que mon explication de la complexité sur le front de la page nedtries a un sens? Peut-être pas.

La clé qui vous manque est la différence entre les bits qui détermine la complexité. Plus la différence est grande, plus le coût de la recherche est faible, tandis que plus la différence est faible, plus le coût de la recherche est élevé. Le fait que cela fonctionne provient de processeurs modernes en panne. Pour simplifier, si vous évitez la mémoire principale, votre code est environ 40-80 fois plus rapide que si vous dépendez de la mémoire principale. Cela signifie que vous pouvez exécuter 50-150 opérations dans le temps nécessaire pour charger une seule chose de la mémoire. Cela signifie que vous pouvez faire un peu d'analyse et déterminer quel nœud nous devrions aller voir dans peu de temps que le temps nécessaire pour charger la ligne de cache pour ce nœud en mémoire.

Ceci supprime efficacement la logique, le balayage des bits et tout le reste de l'analyse de complexité. Ils pourraient tous être O (N^N) et cela n'aurait pas d'importance. Ce qui importe maintenant, c'est que la sélection du prochain nœud à regarder est effectivement gratuite, donc c'est le nombre de nœuds qui doivent être chargés pour l'examen est la contrainte d'échelle et donc c'est le nombre moyen de nœuds regardés sur le nombre total de nœuds, ce qui est sa complexité moyenne, car la lenteur de la mémoire principale est de loin la plus grande contrainte de complexité.

Est-ce que cela a du sens? Cela signifie bizarreries, comme si certains bits sont densément emballés à une extrémité de la clé, mais lâchement empaquetés à l'autre extrémité de la clé, les recherches dans l'extrémité dense seront beaucoup plus lentes (approche O (log N) où N est le nombre d'éléments denses) que les recherches dans l'extrémité faiblement tassée (approche O (1)). Un jour, je vais bientôt ajouter de nouvelles fonctions qui tirent parti de cette fonctionnalité d'essais au niveau du bit, donc vous pouvez dire "ajouter ce nœud à un espace lâche/dense et retourner la clé que vous avez choisi" et toutes sortes des variations sur ce thème. Malheureusement, comme toujours, cela prend du temps et exige du temps.

Niall