From: Robert Klemme <shortcutter@...>
Date: 2008-10-30T16:47:37+09:00
Subject: Re: array comparison

2008/10/30 Chad Perrin <perrin@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?

First of all I would use Set which is far more efficient for these
amounts. You need to make sure that your items in the Set implement
#hash and #eql? properly (see requirements for Hash keys).

Then, I would write a simple program using Sets and see what happens
before I even start to speculate whether it would work or not.  This
program is written in a matter of minutes and if it works you are done
- if not, you may be able to tweak the simple solution to work (e.g.
for example by making sure that there is only one instance of string
values that are frequently seen in the input).

Btw, if you compare two "lists" you only need to keep one in memory to
make some of the checks.

Kind regards

robert


-- 
remember.guy do |as, often| as.you_can - without end