Сравнивать два очень больших сортированных массива эффективно

Question

Мне нужно найти эффективный способ узнать, что отличается между двумя большими отсортированными массивами. Другими словами, мне нужно узнать , что было добавлено/удалено из одного из них на основе сравнений с другим. Сортировка не является обязательной, поэтому, если вы думаете, что мы можем добиться чего-то без заказа, все в порядке со мной.

Эти два массива длиной один миллион элементов, поэтому сравнение их в памяти сразу невозможно.

Фон для этого прост. Я пытаюсь получить все новые строки из удаленной старой таблицы SQL (OpenEdge), которая не имеет никакого способа сообщить, что является новым. Я знаю, это может показаться странным, но это реальность, с которой я работаю. Таким образом, никаких триггеров по данным, никаких временных меток, ничего. Это было разрешено в другом потоке StackOverflow, поэтому Я не ищу способы добавить эту функцию в удаленный стол.

У меня есть копия этой таблицы в локальной базе данных Postgresql, чтобы помочь в сравнении. Я делаю сравнение по сети и используя jRuby с драйвером JDBC для проверки удаленных данных. До сих пор я пытался загружать обе таблицы в массивы Ruby и делать стандарт array - array, но это поглощает, почему слишком много памяти (таблицы составляют миллион строк).

Какие-либо другие варианты для меня рассмотреть? Любые алгоритмы, о которых я не знаю?

Answer 1

Если оба массива уже отсортированы, вы можете одновременно пройти через оба массива и сравнить элементы, используя индекс для каждого массива. Если элементы с индексом i и j равны, то продвигайте оба индекса. Если элементы разные, то просто продвигайте индекс, где элемент в массиве меньше, чем элемент в другом массиве.

Вот код этого метода. Обратите внимание, что он принимает оба массива сортируются и элементы можно сравнить с помощью ==, < и >:

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

И простой тест

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(', ') 

Выход:

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

Другой вариант может делать symmetric difference непосредственно в SQL, как показано здесь: Does the SQL spec provide for a better way to do a exclusive ORing of two sets?

SELECT COALESCE(A.id, B.id) AS id 
FROM InitialTable A 
FULL OUTER JOIN TableToCompareWith B 
ON A.id = B.id 
WHERE A.id IS NULL OR B.id IS NULL