Ternary Search Trees

[Robert Fraser]

bearophile wrote:
> 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).

Yes, it's a map (for my use case).

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

Attached, if you don't mind NO comments.

I really want to port this: 
http://dasnar.sdf-eu.org/res/ctst-README.html ... The automatic 
balancing might make it a lot better if elements are inserted in order. 
It might be very easy by replacing the malloc/free calls with 
gc_malloc/gc_free calls.

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

I think Phobos1's AAs were pretty bad, but have you tried 
Tango's/druntimes? They're quite optimized (they're implemented as a 
hash with trees used for collisions).
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: array.d
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20090424/2044e6a8/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: memory.d
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20090424/2044e6a8/attachment-0001.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: tst.d
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20090424/2044e6a8/attachment-0002.ksh>