tries

essais

Cette classe fournit la base pour construire un conteneur à base de trie.

Sur sa forme de base, la classe Ttrie peut être utilisée pour stocker des éléments de données basés sur 16, 32 et 64 bits.

La structure fournit une implémentation de trie à profondeur fixe, ce qui rend à son tour un temps égal pour trouver, supprimer et ajouter des nœuds.

L'ordre de la structure est o (d) où d est la profondeur du Trie, qui dépend si elle est construite pour stocker 16, 32 ou 64 bits. Pour 16 bits d = 4 pour 32 bits d = 8 et pour 64 bits d = 16

Pour garder la taille du nœud petite, seulement 16 branches par nœud seront utilisées et les drapeaux indicateurs et les indices de pointeur interne sont codés en mot de 16 bits et dans un entier de 64 bits.

Les pointeurs vers les branches sont gérés dynamiquement, donc seul un pointeur est alloué sur le réseau de pointeurs lorsqu'une nouvelle branche doit être ajoutée, ce qui minimise le gaspillage du réseau de pointeurs pré-allocalisé vers des branches de niveau inférieur. Il va le ralentissement ajoute cependant.

Les feuilles sont allouées sur place plutôt que comme des nœuds individuels pointés par le dernier nœud de branche.

Enfin, les nœuds de feuilles peuvent être contrôlés dynamiquement par la classe dérivée de Ttrie permettant une implémentation facile des dictionnaires en utilisant Ttrie comme base.

Dans l'ensemble, effectuant certains tests stockant la mémoire allouée par l'allocateur de Lazarus (freepascal) dans un Mac rend environ 40% d'efficacité de stockage proportionnellement à la taille des objets stockés, ce qui n'est pas mauvais étant donné les performances pour les opérations ADD, Find et supprimer les opérations.

La classe fournit également une méthode de pack utilisée pour garder le stockage en échec lorsque beaucoup de supprimés ont été émis.

Tintegerhashtrie et Tstringhashtrie sont fournis comme descendants de la classe générique Thashtrie. Thashtrie a deux modes de fonctionnement:

• Utilisez une table de hachage pour le nœud racine, avec une structure de trie avec 16 nœuds par seau pour le niveau suivant
• Structure complète de la hachage du nœud racine

Hash Table fournit de meilleures performances bien sûr, mais Hashtrie a une empreinte mémoire plus efficace lors du stockage d'un petit nombre d'éléments.

Testé TStringhashtrie contre les classes Tdictionary <> et C # Dictionary <>.

TStringhashtrie bat les implémentations C # et Delphi. La différence est plus grande lors de la table de hachage utilisée pour le nœud racine.

L'empreinte de la mémoire dans l'ensemble pour les charges importantes est également meilleure, allant de 30% à 40% mieux. Pour un petit nombre d'éléments, l'utilisation de hashtrie pure plutôt que le nœud racine de table de hachage utilisera considérablement moins de mémoire.

Les tests compilés dans Delphi 2007 ont produit des résultats encore meilleurs car les chaînes n'ont pas eu à subir une conversion de l'UTF16 en ANSI avant d'insérer dans la structure.

TSTRINGHASHTRIE PARTICE UNICODE sous forme UTF8.