大きなファイルのファイル差分

Question

私はこのタスクをjavaでコーディングする必要があります。 私は、それぞれが5GBの2つの大きなファイルを持っていて、複数の行のテキストデータを含んでいます。各行は、カンマで区切られたフィールドの行です（例： "name、empId、designation、address、...、最大30フィールドまで"）。これらの2つのファイルを読んで、別のファイルにレコードを書き込む必要があります。このフィールドは、指定されたデータ行が変更、変更、追加、削除されたことを指定します。 例えば

はFile1

トム、E100、エンジニア

リック、E200、エンジニア

File2の

トム、E100、マネージャー

ポール、 E300、書記官

ResultFile

トム、E100、マネージャー、変更

ポール、E300、書記官、追加

リック、E200、エンジニア、私が使用し

アプローチを作成することです削除されましたempIdをキーとして使用し、データ行全体を値として（empIdが一意であると仮定して）file1のデータからマップを作成し、file2から各レコードを読み取ってマップのデータをチェックします（file2の全内容をメモリに読み込まない、bマップを作成するにはfile1のみ）。私は、BufferedReader/BufferedWriterを読み書きするために使用しています。

このアプローチは正常に機能しますが、小さなデータファイルに対してのみ有効です。私のプログラムは、GBに実行されるデータファイルがあれば、マップを作成しようとしている間にすぐにメモリ不足になります。

メモリと実行速度の両方でこのタスクを達成するための正しいアプローチは何でしょうか？

おかげで、 LX

Answer 1

異なるアプローチがキーに基づいて、各ファイルにexternal sortを行い、その後、並行して、それらを反復することができます。

ハイレベル擬似コード：外部ソートを行って、次のループは、メモリの一定量を使用する場合、少ないメモリ署名を用いて行うことができる

sort(file1) 
sort(file2) 
iter1 = file1.begin() 
iter2 = file2.begin() 
while (iter1 != file1.end() && iter2 != file2.end()): 
    element1 = iter1.getElement() 
    element2 = iter2.getElement() 
    if element1.key() == element2.key(): 
    // same element, check if changed 
    iter1 = iter1.next() 
    iter2 = iter2.next() 
    else if element1.key() < element2.key() 
    // element1 is not in file2, so it is removed. 
    iter1 = iter1.next() 
    else 
    // element2 is in file2 but not in file1, so it's added 
    iter2 = iter2.next() 

while (iter1 != list1.end()): 
    element1 = iter1.getElement() 
    // element1 is removed 
    iter1 = iter1.next() 

while (iter2 != list2.end()): 
    element2 = iter2.getElement() 
    // element2 is added 
    iter2 = iter2.next() 

これはソート必要。 複雑さはO(mlogm + nlogn)です。n,mはリストのサイズです