[REBOL] Essay on Associative Data Stores Re:(2)
From: joel:neely:fedex at: 19-Sep-2000 7:44
Hi, Ole!
[ole_f--post3--tele--dk] wrote:
[snip]
> I've attached some functions for manipulating with an associative
> data structure. I personally think they suffice for my normal uses,
> but I'm looking forward to your comments (though, please keep it
> short then, I don't have the time to read through all that
> ASCII ;-) ).
>
(Not only do you not have time to read it, I really don't have time
to be typing it! ;-)
I'll wait to respond with specifics until I've had a chance to look
them over adequately. I'm curious about the motivations (and
the performance) of your compromise solution -- part object, part
function library.
Would I be correct in guessing that you chose to make associate-ads
and lookup-ads standalone functions instead of object methods to
avoid the duplication which REBOL (currently -- hint, hint, hint)
imposes on objects?
> BTW, using a hash! for the "keys" array would probably be a better
> idea than just using a block!, as I currently do. _If_ find/only
> works faster on hash! lists, that is (it should be, but I don't
> know).
>
Disclaimer: I've not done the empirical testing of this hypothesis
for the REBOL implementation of hash! , so PLEASE take this as
speculation.
My general experience is that hashing vs. array/list lookup is
subject to tradeoffs. There is overhead (both space and time)
with hashing, which makes it perform more poorly than simpler
but straightforward lookup schemes for small cases. As the size
of the data collection grows, however, that overhead amortizes
nicely. Ultimately, for "large enough" collections of data,
the hash table beats array/list algorithms -- the best way to
determine how large is large enough, of course, is to run some
benchmarks, which I'd like to do some time when my higher
priorities have been handled (and there are LOTS of them! ;-)
-jn-