tries
1.0.0
Diese Klasse bietet die Grundlage für den Bau eines Trie -basierten Behälters.
In seiner Grundform kann die TTRIE -Klasse verwendet werden, um Datenelemente von 16, 32 und 64 Bits zu speichern.
Die Struktur bietet eine feste Tiefen -Trie -Implementierung, die auch die gleiche Zeit zum Suchen, Entfernen und Hinzufügen von Knoten verleiht.
Die Reihenfolge der Struktur ist o (d), wobei d die Tiefe des Tries ist, was abhängt, wenn es auf die Speicher von 16, 32 oder 64 Bits gebaut wird. Für 16 Bits D = 4 für 32 Bit D = 8 und für 64 Bit D = 16
Um die Knotengröße klein zu halten, werden nur 16 Zweige pro Knoten verwendet und Indikatorflags und interne Zeigerindizes werden in einem 16 -Bit -Wort und in einer 64 -Bit -Ganzzahl codiert.
Zeiger auf Zweige werden dynamisch verwaltet, sodass nur ein Zeiger auf dem Zeiger-Array zugewiesen wird, wenn ein neuer Zweig hinzugefügt werden muss. Dies minimiert die Verschwendung von vorab assoziertem Zeiger-Array zu niedrigeren Zweigen. Es wird jedoch verlangsamt.
Blatt werden eher als einzelne Knoten zugewiesen, die vom letzten Zweigknoten gerichtet sind.
Schließlich können Blattknoten von der abgeleiteten Klasse von Ttrie dynamisch gesteuert werden, die eine einfache Implementierung von Wörterbüchern mit Ttrie als Basis ermöglichen.
Insgesamt werden einige Tests zum Speichern des von Lazarus (freepascal) Allocator in einem Mac zugewiesenen Speicher rund 40% Speichereffizienz proportional zur Größe der gespeicherten Objekte verleiht, was angesichts der Leistung für das Hinzufügen, Finden und Entfernen von Vorgängen nicht schlecht ist.
Die Klasse bietet auch eine Packmethode, mit der der Speicher in Schach bleibt, wenn viele entfernt wurden.
Tintegerhashtrie und Tstringhashtrie werden als Nachkommen der Thashtrie Generic Class bereitgestellt. Thashtrie hat zwei Betriebsmodi:
Die Hash -Tabelle bietet natürlich eine bessere Leistung, aber Hashtrie hat eine effizientere Speicherpflege bei der Speicherung einer geringen Anzahl von Elementen.
Getestet Tstringhashtrie gegen Delphis TDictionary <> und C# Dictionary <> Classen.
Tstringhashtrie schlägt sowohl im Implementierungen von C# als auch C# und Delphi. Der Unterschied ist größer, wenn die Hash -Tabelle für den Stammknoten verwendet wird.
Der Speicher Fußabdruck insgesamt für große Lasten ist auch besser und liegt zwischen 30% und 40% besser. Für eine geringe Anzahl von Elementen verwendet der Stammknoten mit reinem Hashtrie eindeutig weniger Speicher.
In Delphi 2007 zusammengestellte Tests führten zu noch besseren Ergebnissen, da die Saiten nicht von UTF16 zu ANSI konvertieren mussten, bevor sie in Struktur eingefügt wurden.
Tstringhashtrie unterstützt Unicode in UTF8 -Form.
