두 개의 매우 큰 정렬 된 배열을 효율적으로 비교하십시오.

Question

두 개의 큰 정렬 된 배열간에 다른 점을 찾는 효율적인 방법을 찾아야합니다. 다른 말로하면,과의 비교를 기반으로 그들 중 하나에서 추가/삭제 된 내용이 인 것을 찾아야합니다. 정렬은 선택 사항입니다. 따라서 주문이없는 무언가를 달성 할 수 있다고 생각하면 저와 잘 맞습니다.

이 두 배열은 각각 백만 요소 길이이므로 을 메모리에서 동시에 비교할 수 없습니다.

배경은 간단합니다. 새로운 것을 알리는 방법이없는 원격 레거시 SQL (OpenEdge) 테이블에서 모든 새 행을 가져 오려고합니다. 나는 이상하게 들릴지도 모른다는 것을 알고 있습니다. 그러나 그것은 제가 작업하고있는 현실입니다. 데이터에 대한 트리거가 없으며 시간 소인도없고 아무 것도 없습니다. 이것은 다른 StackOverflow 스레드에서 해결되었습니다. 이 기능을 원격 테이블에 추가하는 방법을 찾고 있지 않습니다.

나는 비교를 돕기 위해이 테이블을 내 PostgreSQL 로컬 데이터베이스에 가지고 있습니다. 나는 네트워크를 통해 비교를하고 JDBC 드라이버로 jRuby를 사용하여 원격 데이터를 검사한다. 지금까지 두 테이블을 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