using a binary tree container

[spir]

On 02/12/2011 12:56 AM, Ali Çehreli wrote:
> On 02/11/2011 10:35 AM, spir wrote:
>
>>  D's builtin AAs seem /very/ fast
>>  on key access. You'd probably have a hard time even approaching their
>>  performance using whatever kind of tree (or rather, of trie).
>
> That is expected. D AAs are hash tables, meaning that they provide O(1)
> complexity for element access; compared to the O(log N) complexity of binary
> trees.
>
> For completeness: adding elements is still O(1) for a hash table; compared to
> O(N log N) of a tree.

You are right, but O(1) & O(log N) do not tell the whole story, --they're just 
proportional to a given factor that may be whatever.
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)).
Hash tables actually have an access time firstly depending on hash computation 
time, which can be costly: they are like O(k), where can like for tries often 
depends on key size. Then statistically a linear time O(n) inside "buckets" 
enters the game; hard to manage & evaluate because it depends on average load, 
meaning numbered of elements relative to number of buckets. Then, it's a 
question of pondering time vs space cost.

FWIW, I have implemented tries as fast as library hash tables for a single key 
type in freepascal (without even optimising). And both of those "sophisticated" 
data structures only were worth it above a threshold of about 100 items; I mean 
compared to plain arrays of (key,value) pairs!
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! (again, compared to arrays of 
(key,value) pairs). If you want numbers, search the archives of the PiLuD 
mailing list, I published much data in a thread there (last year): 
http://groups.google.com/group/pilud/
  People, like me, concluded for instance that to implement namespaces it's 
really not worth it to use complicated data structures. We were wrong (I had 
not yet met D's AAs then).

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