Ternary Search Trees

[Robert Fraser]

bearophile wrote:
> Does someone has some need for Ternary Search Trees into Phobos (for D1. And eventually later for D2 too)?
> TSTs allow to find keys, key prefixes, or even keys with holes. Keys are arrays of T, where T is the template type.
> They can be designed to store the keys alone, or as an associative data structure.
> 
> With some benchmarks I have seen that a simple TST implementation is about as fast as the built-in AAs of D (but much slower than Python dicts).
> 
> Bye,
> bearophile

I implemented a version of the TST you posted using Tango + D1... Here 
are my results:

Test                Part                Mean      Median    Max
----                ----                ----      ------    ---
TST                 Insertion           0.0428    0.0338    0.0886
TST                 Iteration           0.0022    0.0022    0.0024
TST                 Lookup              0.0225    0.0223    0.0237
HashMap             Insertion           0.0621    0.0421    0.2205
HashMap             Iteration           0.0035    0.0034    0.0036
HashMap             Lookup              0.0169    0.0168    0.0184
TreeMap             Insertion           0.1045    0.1041    0.1058
TreeMap             Iteration           0.0041    0.0041    0.0044
TreeMap             Lookup              0.0895    0.0892    0.0917
AssocArray          Insertion           0.0262    0.0262    0.0268
AssocArray          Iteration           0.0015    0.0015    0.0016
AssocArray          Lookup              0.0130    0.0129    0.0132

(TreeMap and HashMap are in tango,util.container, AssocArray is the 
built-in D associative array; testing code is attached. Compiled with -O 
-release -inline using DSSS 0.78 and DMD 1.043 on Windows XP x86 SP3).

Indeed, TSTs seem to beat Red-Black BSTs (the implementation Tango's 
TreeMap uses) quite handily, and have faster insert times than hash 
maps, though slower lookup. The big winner here, though, appears to be 
D's built-in associative arrays. I thought they were supposed to be very 
slow, but Tango's implementation, at least, looks pretty good (without 
any re-hashing).

For order-sensitive collections, I'm definitely using TSTs; I'm sold on 
the concept. Not only are they faster, allowing prefix search could be 
very useful. However, the times here are very low (the word file is only 
1.1MB, and my system is fairly fast, though this is memory-dependent not 
CPU-dependent)... I'll try with a larger word list & see what results I get.
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: dstest.d
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20090424/0c7f48ee/attachment.ksh>