From: Michael Neumann <mneumann@...>
Date: 2003-05-26T18:54:24+09:00
Subject: Re: Binary Tree vs. Hash

On Mon, May 26, 2003 at 06:29:23PM +0900, Xiangrong Fang wrote:
> > 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.
> In my program lookup is very freqent, but update is rare. I tried using
> Array.include? , but it seems is using seqential search, not binary. The
> performance is unbearable. Does anyone know if ruby's internal
> Array.include? is using binary search or not?

I am not sure what your program is doing, but if it's something similar to 
a search engine, then you might consider to use an inverted word-list,
which need not loaded into memory at all.

Regards,

  Michael

-- 
ruby -r complex -e 'c,m,w,h=Complex(-0.75,0.136),50,150,100;puts "P6\n#{w} #{h}\n255";(0...h).each{|j|(0...w).each{|i|
n,z=0,Complex(.9*i/w,.9*j/h);while n<=m&&(z-c).abs<=2;z=z*z+c;n+=1 end;print [10+n*15,0,rand*99].pack("C*")}}'|display