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

Hi --

On Sat, 18 Jul 2009, Chuck Remes wrote:

>
> 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.)

I believe the version you had originally, where you do a mapping of
the whole array, will typically use much more memory than the hash
version. Let's say your original array has 1000 inner arrays, with 10
that are considered unique. The mapping will be a new array, also of
1000 elements. The hash will have 10 key/value pairs -- thus much
smaller.


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)