From: Robert Klemme <shortcutter@...>
Date: 2008-10-31T03:34:25+09:00
Subject: Re: array comparison

On 30.10.2008 18:35, William James wrote:
> On Oct 30, 2:47 am, Robert Klemme <shortcut...@googlemail.com> wrote:
>> 2008/10/30 Chad Perrin <per...@apotheon.com>:
>>
>>
>>
>>> I can easily write a program to compare the contents of arrays, of
>>> course.  Ruby's great that way.  In a matter of a minute or so, I could
>>> write a program that compares small numbers of items in a list with small
>>> numbers of items in another list and give me output that consists of
>>> things that appear in both, or those that don't appear in both, or those
>>> that appear in one and not the other.
>>> I find myself contemplating doing much the same thing, but with lists
>>> that contain millions of entries.  I tend to guess that loading each list
>>> into an array and running a direct comparison of them:
>>>  array_1 = [millions of things]
>>>  array_2 = [millions of things]
>>>  array_3 = array1 & array2
>>> . . . would fill up RAM in a hurry and drag system performance on a
>>> typical desktop computer to a standstill.  What sort of approach would
>>> the expert Ruby hackers suggest for achieving much the same ends without
>>> taking all week and risking a stack overflow?
> 
> Array intersection is pretty efficient in Ruby.
> 
> N = 4_000_000
> a = Array.new(N){ rand N }.uniq
> b = Array.new(N){ rand N }.uniq
> p N, a.size, b.size
> 
> time = Time.now
> ha = {}
> a.each{|x| ha[x] = true }
> hb = {}
> b.each{|x| hb[x] = true }
> intersect = []
> ha.each_key{|x| intersect << x  if hb.include? x}
> puts intersect.size
> print Time.now - time, " seconds\n"
> 
> time = Time.now
> puts (a & b).size
> print Time.now - time, " seconds\n"
> 
> 
> --- output ---
> 4000000
> 2528918
> 2527239
> 1597752
> 12.64 seconds
> 1597752
> 5.063 seconds

The comparison is a bit unfair since you include the build time for the 
structure in case of Hash but not for the Array.  You should at least 
also compare just the intersection time.  And while you're at it you can 
also add Set to the mix. :-)

Kind regards

	robert