Datei diff von großen Dateien

Question

Ich brauche diese Aufgabe in Java-Code. Ich habe 2 große Dateien um 5GB jeweils mit Textdaten von mehreren Zeilen. Jede Zeile ist eine Zeile mit durch Kommas getrennten Feldern, zum Beispiel "Name, EmpId, Bezeichnung, Adresse, ... usw. bis zu 30 Felder". Ich muss diese 2 Dateien lesen und schreibe die Datensätze in eine andere Datei mit zusätzlichen Feld, die angibt, dass die angegebene Datenzeile geändert, nicht geändert, hinzugefügt oder gelöscht wird. Zum Beispiel

File1

Tom, E100, Ingenieur

Rick, E200, Ingenieur

File2

Tom, E100, Leiter

Paul, E300, Clerk

Result

Tom, E100, Manager geändert

Paul, E300, Clerk, Hinzugefügt

Rick, E200, Ingenieur, Deleted

Ansatz I verwendet wird, schaffen eine Karte aus den Daten von file1 EmpID als Schlüssel und ganze Datenzeile als Wert mit (unter der Annahme EmpID eindeutig ist) und dann jeden Datensatz von file2 gegen die Daten in der Karte zu überprüfen, lesen (I nicht Inhalt von datei2 in dem Speicher lese , b Verwenden Sie nur file1, um die Karte zu erstellen. Ich verwende BufferedReader/BufferedWriter zum Lesen und Schreiben.

Dieser Ansatz funktioniert gut, aber nur für kleine Datendatei. Angesichts von Datendateien, die in GBs ausgeführt werden, hat mein Programm sehr bald nicht genügend Arbeitsspeicher, während es versucht, die Karte zu erstellen.

Was wäre der richtige Ansatz sein, um diese Aufgabe zu erreichen, sowohl in Bezug auf Speicher und Geschwindigkeit der Ausführung?

Danke, LX

Answer 1

Ein anderer Ansatz könnte sein, ein external sort auf jede Datei auf dem Schlüssel basiert zu tun, und sie dann parallel laufen.

Hohe Pseudocode:

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

Dies erfordert das Sortieren, die mit wenig Speicher Signatur durchgeführt werden kann, wenn eine externe Art zu tun, und die nächsten Schleifen verwenden auch konstante Menge an Speicher. Komplexität ist O(mlogm + nlogn), wobei n,m die Listengrößen sind