D'abord, lisez ceci:
TPT paper
Je me demandais quelles autres options pourraient exister pour organiser des noeuds pour améliorer les performances. Quelque chose de l'ordre post-parent dans un tableau d'octets, comme les TPT, à quelque chose de plus comme un arbre b-order-k; Je me demande quelles bonnes options sont connues en ce moment? Un peu plus sur le problème:
J'ai un moyen extrêmement rapide de trouver des éléments dans un ensemble clairsemé, étant donné le concept d'adjacence à un pointeur donné. Je me demandais comment je pourrais mieux profiter de cela en stockant une patrie trie.ordonnancements physique optimale des nœuds
Vous pouvez faire des suppositions pour savoir si l'accès sera aléatoire, en lecture seule, en écriture rare ou en ajout seul. Veuillez les noter si vous le faites, mais j'ai effectivement utilisé un TPT et les gains étaient assez importants, donc je suis prêt à considérer certaines contraintes.
Mise à jour
Je suppose que cela était dans certains sens un peu clair. Ce que je cherche ici, c'est des moyens d'arranger les choses en mémoire qui optimisent une métrique de performance ou une autre. Les TPT, grâce à certaines astuces, utilisent l'ordre des nœuds pour optimiser les lectures de disque et l'espace par nœud. Je suis curieux de savoir:
Suppression totale, où la structure est entièrement supprimée de la mémoire.
Inserts, en particulier dans les structures densément peuplées.
Supprime, encore une fois, en particulier dans les structures densément peuplées.
C'est vraiment intéressant! Je ne vois cependant pas comment implémenter une carte significative via un DAWG sans compromettre une grande partie de ce qui les rend efficaces. Je suppose que chaque nœud pourrait contenir un hachage, ou quelque chose de similaire, mais je suis extrêmement douteux à ce sujet. –
Dans le document lexique, le DFA minimal est pondéré: Chaque état a un poids, si vous ajoutez les poids le long du chemin à un état final vous obtenez un nombre unique pour chaque mot (en fait vous obtenez un nombre minimal de hachage) que vous peut utiliser comme un index dans un tableau avec vos informations associées. En ajoutant un autre niveau d'indirection, vous pouvez associer un nombre arbitraire d'éléments à un mot. – hmuelner
Je vais réfléchir profondément à cela, mais c'est incroyablement intelligent. –