Skip to content

Instantly share code, notes, and snippets.

@milovidov983

milovidov983/UniqStringProblem.md

Last active May 14, 2021 06:59
Show Gist options
  • Save milovidov983/c55c790a461f2bd2652c62e2edaa71e8 to your computer and use it in GitHub Desktop.
Save milovidov983/c55c790a461f2bd2652c62e2edaa71e8 to your computer and use it in GitHub Desktop.
Download ZIP
Поиск уникальных строк в большом файле с ограничением по оперативной памяти
Raw
UniqStringProblem.md

Поиск уникальных строк в большом файле с ограничением по оперативной памяти

Условия

  • У нас есть условно бесконечный диск на котором есть большой файл ( думаю что 1Тб файла можно считать большим )
  • Для простоты бумем сичтать что файл имеет кодировку ASCII.
  • В файле имеется неопределенное количество строк, единственное что мы о них знаем - что все они заканчиваются символом перевода строки.
  • Есть условное ограничение по памяти в 1Гб
  • Достоверно неизвестно может ли любая из строк поместиться в памяти т.е. теоретически сама строка может быть больше нашего ограничения по памяти (1Гб по условиям)

Задача

Требуется написать код, который подсчитает количество уникальных строк в файле, т.е. таких строк, которые встречаются в файле всего 1 раз.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment