tries
1.0.0
Esta classe fornece a base para construir um contêiner baseado em trie.
Em sua forma básica, a classe TTRIE pode ser usada para armazenar elementos de dados baseados em 16, 32 e 64 bits.
A estrutura fornece uma implementação fixa de TRIE de profundidade, que, por sua vez, torna o tempo igual para encontrar, remover e adicionar nós.
A ordem da estrutura é O (d), onde D é a profundidade do trie, que depende se construído para armazenar valores de 16, 32 ou 64 bits. Para 16 bits d = 4 para 32 bits d = 8 e para 64 bits d = 16
Para manter o tamanho do nó pequeno, apenas 16 ramos por nó serão usados e os sinalizadores indicadores e os índices de ponteiro interno são codificados em uma palavra de 16 bits e em um número inteiro de 64 bits.
Os ponteiros das filiais são gerenciados dinamicamente, de modo que apenas um ponteiro é alocado na matriz de ponteiros quando uma nova ramificação precisa ser adicionada, isso minimiza o desperdício de matriz de ponteiros pré-alocados para ramos de nível inferior. A desaceleração adiciona a desaceleração.
As folhas são alocadas no local, e não como nós individuais apontados pelo último nó do ramo.
Finalmente, os nós foliares podem ser controlados dinamicamente pela classe derivada do TTRIE, permitindo fácil implementação de dicionários usando o TTRIE como base.
Em suma, realizar alguns testes que armazenam memória alocada pelo alocador Lazarus (FreePascal) em um MAC renderiza cerca de 40% de eficiência de armazenamento em proporção ao tamanho dos objetos armazenados, o que não é ruim, dado o desempenho para add, localizar e remover operações.
A classe também fornece um método de embalagem usado para manter o armazenamento sob controle quando muitos removidos foram emitidos.
Tintegerhashtrie e Tstringhashtrie são fornecidos como descendentes da classe genérica de Thashtrie. Thashtrie tem dois modos de operação:
A tabela de hash oferece melhor desempenho, é claro, mas a Hashtrie possui uma pegada de memória mais eficiente ao armazenar um pequeno número de elementos.
Testou tStringhashtrie contra as classes tdictionary de Delphi <> e dicionário C# <>.
TStringhashtrie vence as implementações C# e Delphi. A diferença é maior quando usada tabela de hash para nó raiz.
A pegada de memória em geral para cargas grandes também é melhor, variando de 30% a 40% melhor. Para um pequeno número de elementos definitivamente usando hashtrie puro, em vez de hash tabela root nó, usará dramaticamente menos memória.
Os testes compilados em Delphi 2007 produziram resultados ainda melhores, porque as strings não precisaram passar por conversão de UTF16 para ANSI antes de inserir na estrutura.
TStringHashTrie suporta Unicode no formulário UTF8.
