File diff файлов большого размера

Question

Мне нужно закодировать эту задачу в java. У меня есть 2 больших файла размером около 5 ГБ, каждый из которых содержит текстовые данные из нескольких строк. Каждая строка представляет собой строку разделенных запятыми полей, например «имя, empId, обозначение, адрес, ..., и так далее до 30 полей». Мне нужно прочитать эти 2 файла и записать записи в другой файл с дополнительным полем, которое указывает, что данная строка данных изменена, не изменена, добавлена ​​или удалена. Например

FILE1

Том, E100, инженер

Рик, E200, инженер

File2

Том, E100, менеджер

Пол, E300, Клерк

ResultFile

Том, E100, менеджер Изменено

Пол, E300, Клерк, Added

Рик, E200, инженер Удаляется

подход я использовал это, чтобы создать карту из данных файла1 с использованием empId в качестве ключевой и всей строки данных в качестве значения (при условии, что empId уникален), а затем прочитайте каждую запись из файла2, чтобы проверить данные на карте (я не читаю весь контент файла2 в память , b ut только 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 - это размеры списков