From: Chuck Remes <cremes.devlist@...>
Date: 2009-07-18T08:51:35+09:00
Subject: Re: [Q] removing array duplicates where a subset is unique


On Jul 17, 2009, at 5:39 PM, David A. Black wrote:

> 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 and Joel,

you both provided the same solution. I will test this to see what kind  
of performance I get. It will be hell on memory, but I assumed any  
solution likely would be. (And Joel, I have presorted the array prior  
to removing the dupes so I have already taken care of the ordering  
issue.)

Thanks for your suggestions.

cr