From: "Ara.T.Howard" <Ara.T.Howard@...>
Date: 2005-09-07T01:08:03+09:00
Subject: Re: Sorted arrays

On Wed, 7 Sep 2005, Hugh Sasse wrote:

> On Wed, 7 Sep 2005, ruby@danb64.com wrote:
>
>> What I'm trying to accomplish is this:  I am processing a large
>> number of items (almost 100,000 rows) of data and trying to find
>> the duplicate items. [\n inserted by hgs]
>
> If you wish to remove duplicate items, read about uniq ...
>
>> I create an MD5 hash based on all of the
>> elements within each row.  Then I check to see if the MD5 value
>> already exists in the list, and if it does, I know the item is a
>
> Which is basically a search.  You may find in practice that for
> largish number of items, it is quicker to search a Hash or a Set
> than an array.
>
>> duplicate.  If not, then I add it to the list.  Very few of them
>        [...]
>> searching and a lot of inserting going on.  For that reason, it
>> won't be acceptable to re-sort it each time I insert an item.
>
> and Hashes don't get sorted, so they are more suited to this.
>> 
>> Thanks in advance,
>
> Other speed tips I've been gathering are at:
>
> http://www.eng.cse.dmu.ac.uk/~hgs/ruby/performance/
>
> you'll see I was trying to solve a similar problem....

what did you end up doing?  i forgot you were working with csv data - did you
consider using sqlite, loading everything into an in-memory table, and going
from there?  could be very fast and quick to code...

on a related note, i did some research into lookups in c using hahses verses
sorted arrays/bsearch; much to my suprise (as a computer scientist) i found
that, with the exception of HUGE (millions) of entries lookup by bsearch was
and order of magnitude faster than any hashing mechanism i could find.  my
test looked at cdb, hsearch, glib hashing functions, gperf and, for bsearch,
the c library bsearch.  profiling the different programs showed that the
reason the bsearch was faster was speedy was due to lack of function calls
and this is easy to imagine - flipping a pointer around memory with only one
stack frame is about as lightweight as one can get...  anyhow, my tests were
very specific to my application but interesting nonetheless - thought you'd be
interested.

cheers.

-a
-- 
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| Your life dwells amoung the causes of death
| Like a lamp standing in a strong breeze.  --Nagarjuna
===============================================================================