0

Дано: очень большой файл(многократно превышает объем оперативной памяти компьютера) с множеством строк, которые содержат, например, по 1000 символов(кирилица, латиница, цифры, знаки, пробелы) в случайном порядке. В нем специально разбросано 15% дубликатов строк. Необходимо обработать данный файл и создать новый файл, который будет содержать только уникальные строки.

Работаю на python 3.6. Пытался обрабатывать "пачками" по N строк(пока не заполнится оперативная память на 80%), собирая эти пачки в множества и дополняя данными этих множеств новый файл. Неудачно.

Пытался делать то же самое несколько раз(т.е. из итогового "нового" файла также вычленял только уникальные значения и записывал в новый файл по кругу). Неудачно.

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

Может быть есть эффективный метод?

Kosta B.
  • 5,821
  • 3
  • 15
  • 24
Константин
  • 103

1 Answers1

1

Варианты внешней сортировки - допустимы, типа сортировки слиянием с использованием внешних файлов. Потом просто проход по порядку с выявлением дублей.

Но я бы, раз строки длинные - использовал хеширование, и в чем-то типа HashMap - уж не знаю, как оно там в Питоне именуется - хранил указатели на места в файле.

Дальше - если хеши разные - то строки 100% разные, так что для выявления дублей надо работать только со списками в пределах одного хеш-значения, а при хорошо подобранном хеше - это совсем не так и много. Тут уже для каждого списка можно и в память строки закачать, если надо. В результате - после удаления дублей - останутся указатели только на уникальные строки.

Harry
  • 221,325