Как искать повторяющиеся значения в огромном текстовом файле с полмиллионом записей

Question

У меня есть входной текстовый файл, в котором есть данные в виде записей (каждая строка является записью и представляет собой более или менее похожую на таблицу БД), и мне нужно найти дубликаты значений. Например:

Rec1: ACCOUNT_NBR_1*NAME_1*VALUE_1
Rec2: ACCOUNT_NBR_2*NAME_2*VALUE_2
Rec3: ACCOUNT_NBR_1*NAME_3*VALUE_3

В приведенном выше наборе Rec1 и Rec2 считаются дубликатами, поскольку номера ACCOUNT одинаковы (ACCOUNT_NBR1).

Примечание. Файл ввода, показанный выше, является файлом типа разделителя (ограничителем является *), однако тип файла также может быть файлом фиксированной длины, где каждый столбец начинается и заканчивается указанными позициями.

В настоящее время я делаю это со следующей логикой:

Loop thru each ACCOUNT NUMBER
  Loop thru each line of the txt file and record and check if this is repeated.
  If repeated record the same in a hashtable.
  End 
End

И я использую Java API «Pattern» и «BufferedReader» для выполнения вышеуказанной задачи.

Но так как это занимает много времени, я хотел бы узнать лучший способ справиться с этим.

Спасибо, Shibu

Answer 1

Сохраните HashMap из {account_number, occurrences} в памяти (изначально пустой) и просматривайте файл только один раз, устанавливая или увеличивая (в HashMap) количество вхождений каждого номера счета вы сталкиваетесь во время обхода.

Если вам также необходимо распечатать полную информацию о дубликатах номеров счетов, затем выполнить второй обход входного файла, на этот раз распечатав полную информацию о каждом номере счета, где соответствующее число вхождений в HashMap превысило 1 во время предыдущего обхода.

С точки зрения использования памяти, даже если все номера учетных записей в файле размером 500 тыс. Строк различаются, вам потребуется только приблизительно 1 МБ целочисленного хранилища (при условии, что номера счетов являются целыми числами) плюс HashMap накладные расходы, которые должны удобно размещаться несколько мегабайт памяти.