3

стоит задача выполнить поиск дубликатов в текстовом файле размером около 50 Гб. строки длинной от 8 до 32 символов. Для начала просто найти дубликаты и показать их на экране. Как решить подобную задачу в приемлемый срок(до 48 часов) с использованием c#? пытался пробегать и сравнивать построчно, но это не для таких объёмов. Логика подсказывает что нужно файл разделить на M частей по N строк. считывать в память части и там их сравнивать. Но что-то мне подсказывает это вариант не сильно быстрее.

Но может существует какой-то другой вариант?

Deim
  • 662
  • 2
    Это одноразовая задача или подобный поиск нужно будет осуществлять часто? – Alexander Petrov Nov 14 '19 at 07:41
  • Это у вас noSQL БД. Регулярные выражения помогут. – becouse Nov 14 '19 at 07:43
  • Полагаю можно на лету бить файл на кусочки и считывать его параллельно. Дубли можно попробывать поискать по хэшу. Но первый вопрос был правильный - это надо делать на постоянке или разово? – Dejsving Nov 14 '19 at 07:50
  • 1
    Выгрузить эти строки в любую нормальную БД и задача сведётся к тривиальной. – Alexey Ten Nov 14 '19 at 07:51
  • Эта задача регулярная. – Deim Nov 14 '19 at 07:55
  • Хотя подозреваю что для 50GB и sqlite хватит и формальна задача будет решена на C# :) – Alexey Ten Nov 14 '19 at 08:00
  • https://ru.stackoverflow.com/a/532675/184217 – Alexander Petrov Nov 14 '19 at 08:09
  • Строки отсортированы? Если нет, то можно отсортировать их методом сортировки слиянием больших файлов. После сортировки поиск дубликатов - дело тривиальное. – tym32167 Nov 14 '19 at 08:20
  • строки не отсортированные. – Deim Nov 14 '19 at 08:23
  • Строки похожие друг на друга или произвольные? – tym32167 Nov 14 '19 at 08:25
  • Следующая партия 50 гигов будет содержать в основном те же строки или каждая партия файлов в основном с новыми строками? – tym32167 Nov 14 '19 at 08:26
  • Даже не так. Следующая партия файлов как то зависит от предыдущей? Например, если вы ваши 50 гигов в базу запишете, это поможет вам с поиском дубликатов в следующем 50 гиговом файле? – tym32167 Nov 14 '19 at 08:30
  • Если бд для вас не вариант, то смотрите мой коммент про сортировку. – tym32167 Nov 14 '19 at 08:30
  • строки произвольные. новый файл не будет зависеть от предыдущего. Присматриваюсь к варианту с sqllite. Вопрос в производительности этого метода. – Deim Nov 14 '19 at 08:32
  • Если каждый файл независимый, то тогда вам каждый раз придется создавать новую бд, что не имеет особого смысла в плане производительности. Я бы посоветовал сортировку слиянием для больших файлов, информации об этом алгоритме валом. Один минус - вам понадобятся как минимум еще 50 гигов места на диске и скорость алгоритма сильно зависит он производительности диска. – tym32167 Nov 14 '19 at 08:37
  • я ранее не встречался с этими алгоритмом сейчас почитал про него и не совсем понял. в нём идёт речь про сравнение двух файлов. то есть мне придётся сделать копию исходного файла. Но есть также одно Но на мой взгляд. если число повторений будет очень мало, то массив в памяти должен разрастись до больших размеров, так? – Deim Nov 14 '19 at 08:59
  • Смысл алгоритма в том, чтобы разбить файл на мелкие файлы, мелкие файлы отсортировать при записи, и потом мелкие файлы объединять в большой так, чтобы на выходе большой файл получился сортированный. – tym32167 Nov 14 '19 at 09:03
  • Если убрать дубликаты (A,B,C,B,A -> A,B,C), то сколько всего строк ожидается? А то может быть достаточно будет в Dictionary или HashSet всё загрузить. – i-one Nov 15 '19 at 15:16
  • дубликатов ожидается не более 0,5% – Deim Nov 17 '19 at 14:04

0 Answers0