From: "David A. Black" <dblack@...>
Date: 2009-07-18T07:39:59+09:00
Subject: Re: [Q] removing array duplicates where a subset is unique

Hi --

On Sat, 18 Jul 2009, Chuck Remes wrote:

> I need to remove duplicates from an array of arrays. I can't use Array#uniq 
> because some fields are different and not part of the "key." Here's an 
> example where the first 3 elements of each sub array are the "key" and 
> determine uniqueness. I want to keep only the first one I get.
>
>>> a = [[1, 2, 3, 4, 5], [1, 2, 3, 9, 4], [1, 2, 3, 4, 4]]
> => [[1, 2, 3, 4, 5], [1, 2, 3, 9, 4], [1, 2, 3, 4, 4]]
>
> The return value of deduplicating this array should be: [[1, 2, 3, 4, 5]]
>
> Here is my first attempt at solving the problem:
>
>
>>> def dedup ary
>>>   ary.map do |line|
> ?>     dupes = ary.select { |row| row[0..2] == line[0..2] }
> ?>     dupes.first
>>>   end.uniq
>>> end
> => nil
>>> 
> ?> dedup a
> => [[1, 2, 3, 4, 5]]
>
> This works. However, it is *super slow* when operating on my dataset. My 
> arrays contain hundreds of thousands of sub arrays. The unique key for each 
> sub array is the first 12 (of 18) elements. It is taking many seconds to 
> produce each intermediate array ("dupes" in the example above), so deduping 
> the entire thing would likely take days.
>
> Anyone have a superior and faster solution?

See if this speeds it up meaningfully (and make sure I've got the
logic right):

   def dedup(ary)
     uniq = {}
     ary.each do |line|
       uniq[ary[0..2]] ||= line
     end
     uniq.values
   end


David

-- 
David A. Black / Ruby Power and Light, LLC
Ruby/Rails consulting & training: http://www.rubypal.com
Now available: The Well-Grounded Rubyist (http://manning.com/black2)
Training! Intro to Ruby, with Black & Kastner, September 14-17
(More info: http://rubyurl.com/vmzN)