From: Robert Klemme <bob.news@...>
Date: 2005-09-07T00:26:27+09:00
Subject: Re: Sorted arrays

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