Ternary Search Trees

[bearophile]

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

Nice.
Is your TST a map? (not a set).
Are you willing to show me your TST code? Your code is surely better than mine, and there can be few little things that can be tuned.
And are you also willing to add it to Phobos? (I'll port it to Phobos1, it's probably easy to do)?


> 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).

Try comparing the performance of built-in D AAs with Psyco+Python dicts, or a good C++ STL hash set/hash map.
D AAs are slow probably also because Phobos is statically compiled, they aren't a template.


>  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.

With modern CPUs lot of tests become too much fast :-)

Bye,
bearophile