From: "Mauricio Fernández" <batsman.geo@...>
Date: 2003-05-27T01:51:15+09:00
Subject: Re: Binary Tree vs. Hash

On Mon, May 26, 2003 at 10:40:00PM +0900, Dave Thomas wrote:
> >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?

IIRC you were using that for a spam filter or something like that  ?

> >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

Are you sure the given example (80000 words into 16KB) is right?
It just doesn't seem to work according to the reference given in your
page:

16*8*1024/80000
1.63840
 
=> max hashes k = 1. P(false positive) = .46!!

However with 90000 words and 64KB, P(false positive) = .061 (k=4) which
is much better :)

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Because I don't need to worry about finances I can ignore Microsoft
and take over the (computing) world from the grassroots.
	-- Linus Torvalds