Каков наилучший способ сортировки 30 ГБ строк на компьютере с 4 ГБ ОЗУ с использованием Ruby в качестве языка сценариев?

Question

Привет, я видел это как вопрос на собеседовании и подумал, что это интересный вопрос, в котором я не уверен в ответе.

Что будет лучшим способом?

Answer 1

Предполагая, что * nix:

system("sort <input_file >output_file")

"sort" может использовать временные файлы для работы с входными файлами, размер которых превышает объем памяти.У него есть переключатели для настройки объема основной памяти и количества временных файлов, которые он будет использовать, если необходимо.

Если нет * nix, или интервьюер хмурится из-за бокового ответа, тогда я напишувнешний сортировка слиянием .См. Ответ @ psyho для хорошего описания алгоритма внешней сортировки.

Answer 2

Один из способов сделать это - использовать внешний алгоритм сортировки :

1. Считать кусок файла в память
2. Сортировать этот кусок, используя любую обычнуюалгоритм сортировки (например, быстрая сортировка)
3. Вывод отсортированных строк во временный файл
4. Повторяйте шаги 1-3, пока не обработаете весь файл
5. Примените алгоритм сортировки слиянием с помощьючтение временных файлов построчно
6. Прибыль!

Answer 3

Поместите их в базу данных и позвольте базе данных беспокоиться об этом.

Answer 4

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

Когда ваш интервьюер спрашивает «лучший», я думаю, что он / она говорит только о производительности.30 Гб строк - это много данных.Все алгоритмы сравнения-обмена Omega(n logn), так что это займет много времени.Хотя существуют алгоритмы O(n), такие как сортировка по счету, их нет на месте, поэтому вы будете умножать 30 ГБ, и у вас будет только 4 ГБ ОЗУ (учитывая объем обмена ...), поэтому я бы выбрал быстрая сортировка

Ответ 2 (частичный)

Начните думать о подсчете сортировки.Вы можете сначала разбить строки на группы (используя метод сортировки по кругу), по одной на каждую букву.Вы можете отсканировать файл и для каждой начальной буквы переместить строку (поэтому копируйте и удаляйте, не тратя места) во временный файл.Вы можете повторить процесс для первых 2, 3 или 4 символов каждой строки.Затем, чтобы уменьшить сложность сортировки большого количества файлов, вы можете отдельно отсортировать строку внутри каждого (используя быструю сортировку сейчас) и, наконец, объединить все файлы по порядку.Таким образом, у вас все еще будет O(n logn), но на довольно низком n

Answer 5

Системы баз данных уже хорошо справляются с этой конкретной проблемой.

Хороший ответ - использовать алгоритм сортировки слиянием, адаптируя его для спулинга данных на диск и с диска по мере необходимости для шагов слияния. Это можно сделать с минимальными требованиями к памяти.