From: Dave Thomas <dave@...>
Date: 2003-05-26T22:40:00+09:00
Subject: Re: Binary Tree vs. Hash

Xiangrong Fang wrote:
> 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?
> 
> 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.

If you're looking for memory efficiency are are simply doing lookups, 
perhaps you should look at using a Bloom filter. You could pack a 90,000 
word dictionary into 64kb. By coincidence my latest Kata is about them:

http://pragprog.com/pragdave/Practices/Kata/KataFive.rdoc,v



Cheers


Dave