From: ruby@...64.com
Date: 2005-09-07T04:32:04+09:00
Subject: Re: Sorted arrays

Thanks for the help.  I switched it to use a Hash, and that performed MUCH better.  The data is not coming from any SQL server--it is just a flat file.  The Ruby script processes it into a format so that it can be BCP'd into MS SQL Server.  And when the table that it gets BCP'd into has a unique constraint on the MD5 hash field--hence the need for me to eliminate the duplicate values beforehand.  Granted, I could have changed the process of importing the data so that this unique constraint was not necessary, but it seemed better to me to eliminate the duplicates using Ruby in this case.

Thanks again,

Dan

From Robert Klemme <bob.news@gmx.net> on 6 Sep 2005:

> 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...
> 
> > 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
> 
> Kind regards
> 
>     robert
> 
> 
>