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
