From: "Ara.T.Howard" <Ara.T.Howard@...>
Date: 2005-09-07T00:51:30+09:00
Subject: Re: Sorted arrays

On Wed, 7 Sep 2005, Robert Klemme wrote:

> ruby@danb64.com wrote:
>> I'm a relative newcomer to Ruby.  Most of my experience is in Delphi.
>> And in Delphi one of the most commonly-used classes is TStringList,
>> which is sort of analogous to ruby's Array (Delphi also has dynamic
>> arrays and static arrays).  TStringList has a property called Sorted,
>> which if set to True makes it possible to insert strings into the
>> list and have it maintain them as a sorted list (without having to
>> re-sort it each time).  Then you can use the IndexOf method (or the
>> Find method) to do a binary search on the list, so you can quickly
>> find the element you're looking for.  My question is whether Ruby has
>> anything like this.  It seems like one could create a descendant of
>> Array that does this.
>
> This comes up once in a while.  I think there is an implementation of a
> tree as well as sorted arrays in the RAA.  However...

this one is great:

   http://raa.ruby-lang.org/project/ruby-rbtree/

it'd be great if it were part of the stdlib imho...

>> 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.
>> 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 duplicate.  If not, then I add it to the list.  Very few
>> of them items are duplicated, so most of the time it will be trying to
>> locate the value in the list, and then immediately after that inserting the
>> same value into the list.  So there will be a lot of 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.
>
> This problem is most easily solved with a Hash or Set: lookups are much
> faster than binary search on a sorted array.  Only downside is that memory
> usage of these is typically worse than that of an array for large data sets.
> But it's worth a try as this is an easy change to your app.
>
> If you draw the data from a RDBMS you should use that for finding
> duplicates.  You can do something along
>
> select key1, key2, key3, count(*)
> from your_table
> group by key1, key2, key3
> having count(*) > 1

great idea - with sqlite you can even do this in-memory and, of course, w/o a
server.

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