From: William James <w_a_x_man@...>
Date: 2008-10-31T02:39:16+09:00
Subject: Re: array comparison

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