두 개의 매우 큰 목록 간의 차이점을 찾으십시오.

Question

두 개의 큰 목록 (1 억 항목 일 수 있음)이 있으며, 각 목록의 원본은 데이터베이스 테이블이나 플랫 파일에서 가져올 수 있습니다. 두리스트는 비교할 수없는 크기이며 둘 다 정렬되지 않습니다. 나는 그들 사이의 차이점을 찾아야한다. 그래서 나는 3 가지 시나리오를 가지고 있습니다 :
1. List1은 데이터베이스 테이블입니다 (각 행은 단순히 하나의 항목 (키)가 문자열이라고 가정합니다). List2는 큰 파일입니다.
2. 두 목록은 모두 2 db 테이블에 있습니다.
3. 두 목록은 두 개의 파일에 있습니다. 경우 2

, 내가 사용할 계획 :

 
select a.item from MyTable a where a.item not in (select b.item form MyTable b) 

이 분명 비효율적 더 좋은 방법이 있나요?

또 다른 방법은 다음과 같습니다
나는 각 목록을 정렬 한 다음은 diff를 찾기 위해 둘을 걸어 할 계획입니다. 목록이 파일에서 온 것이면 먼저 db 테이블로 읽은 다음 db sorting을 사용하여 목록을 출력해야합니다. 실행 시간 복잡도가 여전히 데이터베이스 정렬에서 O (nlogn)입니까?

어떤 접근 방식이든 고통스럽고 관련된 목록에 수억 개의 항목이있는 경우 매우 느립니다. 어떤 제안?

Answer 1

이것은 실제로 데이터베이스 질문이 아닙니다.

1 단계. 두 목록을 모두 정렬하십시오. 어쩌면 db 목록이 이미 정렬되었지만 그렇지 않다면 정렬 된 순서로 내보내거나 동일한 목록이 여러 번 정렬되어야하는 경우 인덱스를 만들 수 있습니다.

2 단계. 정렬 유틸리티를 사용하여 목록의 정렬 된 복사본을 텍스트 파일로 만듭니다. 이 목록이 UNIX sort 유틸리티의 기능을 능가하지 못하면이를 분리하고 각각을 정렬하고 응용 프로그램에 이들 목록을 병합하십시오.

3 단계. 응용 프로그램을 작성하여 두 목록에 대해 병합 알고리즘을 적용하고 차이점을 식별하십시오. 텍스트 파일이 여러 청크 인 경우 주 알고리즘을 정렬 된 순서로 제공하려면 보조 병합 알고리즘이 필요합니다.

UNIX 또는 Linux를 사용하여 텍스트 파일을 정렬 할 수없는 경우 UNIX sort 명령의 소스 코드를 가져 와서 O/S로 이식하십시오. This article explains why.

Answer 2

1. 모든 시나리오에서 데이터베이스에 두 세트를 모두 가져 오십시오 ... 이러한 종류의 정렬 및 결정은 db의 목적입니다. 다른 것은 휠을 재발 명하게 될 것입니다.

2. 다음은 아마 NOT IN보다 빠를 수 (그러나 확인하기 위해 테스트)합니다

   왼쪽이 ON을 MyTable B 가입을 MyTable에서

   선택 a.item A.JoinColumn = B.JoinColumn B.JoinColumn IS NULL

JoinColumns가 인덱싱되어 있는지 확인하십시오. 인덱싱을 통해 정렬 문제를 해결할 수 있습니다.