빠른 데이터 추출 알고리즘

Question

2 utf-8 텍스트 파일이 있어야합니다. 파일의 각 행에는 Ü, Ö, ą, ª와 같은 언어 특정 문자를 포함 할 수있는 문자열이 있습니다. 문자열은 무작위 순서 및 길이이며 반복 될 수 있습니다. 첫 번째 파일에는 적어도 3 백만 건의 행이 있습니다 (1mld 행을 넘는 것은 쉽습니다). 두 번째 파일은 작아서 일반적으로 약 400,000 행을 얻습니다 (그러나 훨씬 더 커질 수 있음).

파일 2에 나타나는 제거 된 항목이있는 파일 1의 항목과 모든 반복 항목을 포함하는 새 파일을 만들어야합니다.

현재 두 파일을 모두 정렬하고 반복되는 항목을 제거합니다. 다음으로 두 번째 파일에 새 파일이 있는지 확인하면서 새 파일에 쓰고 있습니다.

더 빠른 방법이 있습니까?

편집

메모리에 문제가 있습니다. 이 문자열을 메모리에 복사하지 않고 파일을 구매하십시오. 친구는 메모리에 복사하지 말고 파일 스트림에서 작업 할 것을 제안했습니다. 이 실행 시간이 상당히 지난 후에.

컴퓨터 관리자는 데이터베이스에 데이터베이스를 설치하고 싶지 않습니다.

은 후 종류의 루프에서이 같은 내 코드의 룬 : 해시 설정

if stringFromFile1 < stringFromFile2 then writeToFile3 and get next stringFromFile1 
else if stringFromFile1 == stringFromFile2 then dropStringFromFile1 and get next stringFromFile1 
else if stringFromFile1 > stringFromFile2 then get next stringFromFile2 and go to line 1 

Answer 1

사용 가능한 데이터 구조가있는 경우와 같은 당신은 단지 파일을 반복 처리 각 행을 추가 할 수 있습니다. 세트는 반복 및 해시를 허용하지 않습니다 은 요소가 이미 존재하는지 확인하는 끊임없는 방법을 제공해야합니다 (Java에서는 적어도 add 메서드는 요소가 존재하는지 검사하고, 존재하지 않으면 요소를 일정 시간에 설정).

일단 두 파일을 모두 살펴 본다면 해시 집합을 반복하고 해당 내용을 파일에 저장할 수 있습니다. 이렇게하면 선형 시간 내에 알고리즘을 제공 할 수 있습니다.

언급을 잊어 버렸습니다. 메모리 사용량에 제한이 없다고 가정합니다. 그렇다면 각 행의 해시를 기본 키로 사용하여 각 행을 데이터베이스에 저장해보십시오. 두 개의 기본 키가있는 요소를 삽입하면 데이터베이스에 고유 한 문자열이 있는지 확인해야합니다. 삽입을 완료하면 데이터베이스의 값을 검색하여 파일에 저장할 수 있습니다.

Answer 2

제 제안은 파일 2를 사전 처리하고 그로부터 트리 구조를 형성하는 것입니다.

bad 
bass 
absent 

은 다음 트리 구조는 다음과 같이 될 것이다 : 예를 들어, 파일이 이런 종류의가 있다고

BEGIN -> b -> a -> d -> END 
|    | 
|    + -> s -> s -> END 
| 
+-> a -> b -> s -> e -> n -> t -> END 

END 단어 구분 기호 (이 공간 또는 새로운 라인 또는 뭔가 다른 일을) 지정

그러면 파일 하나를 파일 스트림으로 열고 바이트 단위로 읽습니다. 일단 파일의 시작 부분을 만나거나 분리 문자 다음에 오는 문자를 선택하면 나무를 걷기 시작합니다. 스트리밍 된 바이트가있는 경우 END으로 이동하면 일치하는 단어를 발견 했으므로 삭제해야합니다. 그렇지 않은 경우 단어는 고유하며 삭제할 필요가 없습니다. 고유 한 것으로 발견되면 단어를 트리 구조에 추가하여 추가 반복을 무시해야합니다.

트리 구조는 상당한 양의 메모리를 취할 것입니다,하지만 가능한 최적화가 있습니다

Answer 3

배열 일종의 독특한 단어를 잡고보다는 어쨌든 적습니다.

Roman Saveljev가 제안했듯이 메모리에 트리 구조를 유지할 수 있습니다. 데이터의 엔트로피에 따라 쉽게 메모리에 저장할 수 있습니다.

두 번째 파일이 정렬되면 이진 검색을 실행하여 레코드가 있는지 확인할 수 있습니다 (아직 수행하지 않은 경우).

블룸 필터를 메모리에 보관하여 복제되지 않은 레코드를 쉽게 검사하여 매번 디스크에 가지 않도록 할 수 있습니다.