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

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

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


ruby sorting algorithm theory
person Cristiano Fontes    schedule 17.01.2011    source источник
comment
Звучит как алгоритм «разделяй и властвуй», когда результаты сохраняются в отдельных файлах, а затем объединяются в конце.   -  person Omar    schedule 17.01.2011

Ответы (5)


arrow_upward
8
arrow_downward

Предполагая *никс:

system("sort <input_file >output_file")

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

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

person Wayne Conrad    schedule 17.01.2011
comment
Спасибо, это именно то, что я думаю, что ответ должен быть ... Я не знаю * nix, но я думаю, что в какой-то момент он указан в вопросе. - person Cristiano Fontes; 17.01.2011

arrow_upward
5
arrow_downward

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

person Ignacio Vazquez-Abrams    schedule 17.01.2011

arrow_upward
5
arrow_downward

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

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

arrow_upward
3
arrow_downward

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

Когда ваш интервьюер спрашивает о лучшем, я полагаю, что он / она говорит только о производительности.

Ответ 1

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

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

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

person usr-local-ΕΨΗΕΛΩΝ    schedule 17.01.2011

arrow_upward
2
arrow_downward

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

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

person yfeldblum    schedule 17.01.2011