From: Brian Candler <b.candler@...>
Date: 2008-10-30T18:08:21+09:00
Subject: Re: array comparison

Chad Perrin wrote:
> 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?

If these millions of things are being read from disk, then sort them 
first (*). Then you can do a sort-merge to check which are in one but 
not the other.

Roughly: Read the first item from both and compare them. If they're 
equal, munch them both. If the item from A is smaller than the item in 
B, then munch the item from A (since it exists in A but not B), and vice 
versa. An efficient implementation might read a few thousands items from 
both A and B into local buffers first.

The Sedgewick "Algorithms" book has chapters on external sorting and 
searching.

HTH,

Brian.

(*) Of course, the problem then becomes one of sorting millions of 
things, but this is a well-solved problem. The unix "sort" command-line 
tool will happily sort files which are much larger than available RAM, 
by dividing into smaller chunks and sort-merging them. Just take care to 
set LC_ALL properly; otherwise sort behaves in a very strange way. 
LC_ALL=C seems to work best for me.

Once the inputs are sorted, an '&' or '|' operation implemented as above 
will generate an output which is already sorted.

The unix 'join' command can do these operations for you, too.
-- 
Posted via http://www.ruby-forum.com/.