Используйте внешнюю сортировку слиянием. Файл на 100 ГБ не поместится безопасно в 100 ГБ RAM после разбора, создания объектов, буферов и учёта памяти ОС.
Эффективная сортировка гигантского файла
Используйте внешнюю сортировку слиянием. Файл на 100 ГБ не поместится безопасно в 100 ГБ RAM после разбора, создания объектов, буферов и учёта памяти ОС.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Дан файл объёмом 100 ГБ, а доступная оперативная память также составляет 100 ГБ. Требуется выполнить сортировку данных в файле за минимальное время, используя ресурсы максимально эффективно.
Ответ
Используйте внешнюю сортировку слиянием. Файл на 100 ГБ не поместится безопасно в 100 ГБ RAM после разбора, создания объектов, буферов и учёта памяти ОС.
Читайте ограниченные блоки, сортируйте каждый и сохраняйте временные отсортированные серии. Затем выполняйте многопутевое слияние через небольшую кучу и последовательное чтение. При слишком большом числе серий нужны несколько проходов.
Размер блока и параллелизм выбирайте по измерениям, оставляя память системе; Python-объекты могут многократно превышать размер текста. Нужны запас временного диска, согласованный формат записей и порядок сравнения. Для строковых данных подходит системный sort с явно заданными лимитами. Результат пишите отдельно и заменяйте исходный файл только после успешного завершения.