From: "Mauricio Fernández" <batsman.geo@...>
Date: 2003-05-28T14:39:29+09:00
Subject: Re: Binary Tree vs. Hash

On Wed, May 28, 2003 at 01:49:53AM +0900, Robert Klemme wrote:
> 
> "ahoward" <ahoward@fsl.noaa.gov> schrieb im Newsbeitrag
> news:Pine.LNX.4.53.0305271517520.28367@eli.fsl.noaa.gov...
> > On Tue, 27 May 2003, Robert Klemme wrote:
> >
> > > IMHO that's overly complicating Array. An Array is simply a sequence
> of
> > > items.  Period.
> >
> > on paper - sure.  but in reality we have:
> >

We cannot optimize w/ the @sorted flag because Array is used for two
different purposes:
 * poor man's set (sorting would help here for include? and the like)
 * plain old array (you don't want sorting as you expect to find one
   element at the index you inserted it)

Unless we create 2 classes specifically for these 2 different semantics,
nothing can be done.

So if anything, the first step would be creating a Set class. Set
objects could be hinted on creation whether to use internally a
sorted array, a hash ( object => true ), etc, depending on the desired
complexity and space/time trade-off.

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

* JHM wonders what Joey did to earn "I'd just like to say, for the record,
  that Joey rules."
	-- Seen on #Debian