Сравните два больших файла, у которых нет ни одной общей строки

Question

У меня есть два больших (10M строк) файла, оба файла данных. Каждая строка содержит несколько полей, последние 3 поля задают положение x, y, z.Чтобы проверить свой генератор случайных чисел, я хочу быть уверен, что в одном файле нет ни одной строки с позицией, идентичной любой строке в второй файл. Единственное, что случилось со мной, это что-то вроде

loop over file1
   read file1: eventnr1 energy1 posX1 posY1 posZ1
   loop over file2
      read file2: eventnr2 energy2 posX2 posY2 posZ2
      if ( fabs(posX1 - posX2) < 0.00001 && fabs(posY1 - posY2) < 0.00001 etc...)

Конечно, это очень трудоемко (я пробовал и сценарий bash, и программу на C ++, я не уверен, что будет быстрее. ). Кто-нибудь знает более умный (быстрый) способ?

Для ясности, файлы могут быть совершенно разными, за исключением одной или двух строк. Использование UNIX "diff" не будет работать (слишком большие файлы).

С уважением,

Machiel

Answer 1

0) Если у вас достаточно ОЗУ для хранения полей меньшего файла в ОЗУ, вы можете это сделать.
0 a) Сохраните его в HashMap (если вы можете себе позволить накладные расходы и можете использовать ha sh -функция, которая хеширует числа, которые настолько похожи, что вы предполагаете, что они совпадают с одним и тем же значением) -> проверяет стоимость O (1)
0 б) Сортировать поля в ОЗУ (стоит O (n * log n) и проверяет стоимость позже O (log n) )

Перебирайте файл, которого нет в оперативной памяти, и проверяйте каждый значение, если оно у вас уже есть в ОЗУ.

Таким образом, вы читаете оба файла только один раз, и затраты будут a) O (n) , b) O (n log n )

---

1) Если вы не можете загрузить меньший файл в ОЗУ: Выполните то же действие, что и в 0) для каждого фрагмента данных меньшего файла. Это означает, что вам нужно прочитать фрагменты (k фрагментов) из одного файла и для каждого перебрать другой файл.

Таким образом, вы читаете меньший файл один раз, а другой k раз. Затраты: a) O (k n) , b) O (k n / k log n / k + n k * log n / к)

Answer 2

• Прочитать все содержимое обоих файлов
• Сортировать их
• Начните с указателей на первые записи в обоих списках записей и увеличивайте значение, указывающее на меньшую запись, пока не дойдете до end

Это O(N*logN) (для сортировки остальное линейно), по сравнению с O(N*N) с вашим методом грубой силы.