ruby - Compare two very large sorted arrays efficiently -

i need find efficient way of find out different between 2 large sorted arrays. in other words, need find out what added/deleted 1 of them based on comparisons other. sorting optional, if think can achieve no ordering, fine me.

these 2 arrays each 1 million elements long, comparing them in memory @ once not feasible.

the background simple. trying new rows remote legacy sql (openedge) table not have way of telling new. know might sound strange, reality working with. no triggers on data, no timestamps, nothing. resolved in stackoverflow thread i not looking ways add functionality remote table.

i have copy of table in postgresql local database comparisons. doing comparison on network , using jruby jdbc driver inspect remote data. tried load both tables ruby arrays , standard array - array, eats why memory (the tables each million rows long).

any other options me consider? algorithms not aware of?

if both arrays sorted, can go through both arrays @ same time , compare elements using index per array. if elements @ index , j equals, advance both indexes. if elements different, advance index element in array less element in other array.

here's code method. note assumes both arrays sorted , elements can compared through ==, < , >:

def compare_sorted_arrays a1, a2   i, j = 0, 0   output = []   while < a1.length , j < a2.length     if a1[i] == a2[j]       += 1       j += 1     elsif a1[i] < a2[j]       output << a1[i]       += 1     else       output << a2[j]       j += 1     end   end   i.upto(a1.length-1) |x|     output << a1[x]   end   j.upto(a2.length-1) |x|     output << a2[x]   end   output end 

and simple test

puts (compare_sorted_arrays([1, 2, 3, 4,], [1, 3, 5, 7])).join(', ') puts (compare_sorted_arrays([1, 3, 5, 7], [1, 2, 3, 4,])).join(', ') 

output:

2, 4, 5, 7 2, 4, 5, 7 

another option may doing symmetric difference directly in sql shown here: does sql spec provide better way exclusive oring of 2 sets?

select coalesce(a.id, b.id) id initialtable full outer join tabletocomparewith b on a.id = b.id a.id null or b.id null