From: Robert Klemme <bob.news@...>
Date: 2003-05-26T17:18:35+09:00
Subject: Re: Binary Tree vs. Hash


"Xiangrong Fang" <xrfang@hotmail.com> schrieb im Newsbeitrag
news:20030526135729.583F.XRFANG@hotmail.com...
> Hi ruby fans,
>
> I have a question about algorithm efficiency.
>
> I have used hash in my ruby program. It worked fine. However, I found
> that the memory consumed by a hash is tremendous. While the hash file is
> stored on disk (using pstore) it is merely 100-200KB, but in memory, it
> consumes apporximately 5-10 Megabytes! I don't know if it is related to
> the cache algorithm used by ruby?

How did you measure this?  Is there a way to know the amount of memory
used of an object graph?

> I tried to reduce this memory requirment and thought of using Binary
> Tree. Just did some test in Delphi, it seems good. I loaded an English
> dictionary of about 1M (90000+ lines) it just took about 6-8M of memory,
> seems much better than hash.

I don't think you can compare memory consumption across programming
languages like that.

> Now my question is, since hash is O(1) and BTree is O(LOG(N)), does it
> mean that hash is born to be less storage-efficient than BTree? How can
> I get the best of both BTree and hash?

It's a typical tradeoff: you can't have both - space efficiency AND
minimal memory consumption.  If you *have* to keep memory consumption low
I think there is a tree implementation in the RAA.  Another option would
be to use an Array, keep that sorted and implement (or use) a binary
search, which gives quite similar fetch performance as a tree.  Insert
might or might not be slower.

Regards

    robert