using a binary tree container

spir denis.spir at gmail.com
Sun Feb 13 00:05:03 PST 2011


On 02/13/2011 01:18 AM, Ali Çehreli wrote:
> On 02/11/2011 04:55 PM, spir wrote:
>
>>  Also, trees are not always O(logN): tries () are O(1) for access,
>>  relative to number of elements, in fact their search is not related to
>>  that factor, just like hash table instead to the length of keys
>>  (O(log(length)).
>
> Yep. I should know: I had written a patricia trie in the context of a
> networking ASIC. :)
>
>>  In D, not only there is no way (for me) to even approach builtin AA perf
>>  with tries (even with some search for optimisation), but those deadly
>>  flash-fast AAs are worth it as early as with a few items!
>
> Thank you. It's very good to know that D's AAs are very fast. I had no idea. :)

Beware: I'm not saying this as an absolute truth out of extensive measures. 
Just comparing plain arrays of (key,value) pairs versus tries versus hashed AAs 
in the same language, done in 2 languages only (D and freepascal).

Denis
-- 
_________________
vita es estrany
spir.wikidot.com



More information about the Digitalmars-d-learn mailing list