Эффективная внекорневая сортировка

Я пытаюсь решить, как эффективно сортировать огромный набор данных, который не поместится в памяти. Очевидный ответ на высоком уровне состоит в том, чтобы отсортировать целую кучу кусков, которые подходят в памяти с использованием стандартного алгоритма, записать их на диск и затем объединить. Слияние их - проблема.

Скажем, данные делятся на куски C, поэтому у меня есть файлы C для слияния. Если я делаю слияние C-way за один проход, то технически у меня есть алгоритм O (N ^ 2), хотя тот, который должен выполнять O (N), записывать на диск. Если я итеративно объединять их в файлы C/2, затем файлы C/4 и т.д., Тогда у меня есть алгоритм O (N log N), но тот, который должен выполнить O (N log N), записывать на диск и, следовательно, a огромный постоянный термин.

Каково типичное решение этой головоломки? Есть ли хороший?

Ответ 1

Простой ответ заключается в том, что на этот вопрос нет простого ответа. Есть много ответов, большинство из которых довольно сложны - Том Кнута 3 (для примера) посвящает ему много места.

Одна вещь, которая становится очевидной при просмотре сделанного, состоит в том, что вы действительно хотите свести к минимуму количество файлов, которые вы создаете во время начальной сортировки, и максимизировать длину каждого из них. Чтобы сделать это, вы обычно хотите прочитать примерно столько же данных, сколько можете поместиться в памяти, но вместо того, чтобы просто сортировать его и записывать, вы хотите поместить его в кучу. Затем, когда вы записываете каждую запись, вы читаете В другой записи и помещаете ее в свою кучу. Когда вы записываете каждую последующую запись из кучи в файл, вы проверяете, превышает ли она существующие записи. Если нет, вы удаляете его из кучи и вставляете в другую кучу. Затем продолжайте следующую самую маленькую запись в первой куче. Вы перестаете записывать записи в текущий файл, когда первая куча полностью пуста, а вторая куча занимает всю вашу память. В этот момент вы начинаете записывать записи в новый файл и в основном "свопите" использование двух куч.

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

Edit: Я, конечно, не изобрел этого - я, вероятно, сначала прочитал об этом в Кнуте, но, возможно, в Algorithms + Data Structures = Programs (Niklaus Wirth) - оба обсуждают это. Кнут первым опубликовал метод "Х. Сьюард" в своей магистерской диссертации в Массачусетском технологическом институте в 1954 году. Если у вас есть второе издание Кнута, то оно на стр. 254 тома 3. Я никогда не получал копию третьего издания, поэтому у меня нет номера страницы для этого.

Ответ 2

Хорошим решением является внешняя сортировка. В частности, проверьте алгоритм внешнего слияния.

Внешняя сортировка - это термин для класса алгоритмов сортировки, которые могут обрабатывать огромное количество данных. внешний сортировка требуется, когда данные сортировка не вписывается в основную память вычислительного устройства (обычно RAM), и вместо этого они должны более медленная внешняя память (обычно жесткий диск). Типичный внешний алгоритм сортировки использует сортировку-слияние стратегия, начинающаяся с сортировки небольшие подфайлы. Основной алгоритм состоят из двух этапов: сортировка фазы и фазы слияния. в фаза сортировки, подфайлы могут доступно свободное пространство для буфера в основную память, отсортированную с использованием внутренний алгоритм сортировки и записанный на диск как временный отсортированные подфайлы. На этапе слияния, сортированные подфайлы объединяются во время один или несколько проходов.

Ответ 3

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

"Используйте команду unix sort

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

Поэтому, если вы не планируете повторно изобретать колесо: т.е. у вас есть время, и это критически важно для бизнеса, то просто использование unix sort, вероятно, отличная идея.

Единственным недостатком является его тайный синтаксис. Эта страница посвящена команде и различным объяснениям.

Мой личный совет: возьмите небольшой образец данных для проверки того, что команда эффективно делает именно то, что вы хотите.

Ответ 4

Почему бы не взглянуть на проблему с другой точки зрения. Например, если вы сортируете имена, сделайте проход, отсортировав все, начиная с A-F, строки сортировки второго прохода, начинающиеся с G-M и т.д. Затем результаты можно просто добавить в порядок. Недостатком является то, что данные должны считываться с диска C раз.

Ответ 5

Ник прав, используйте внешнюю сортировку. Кстати, слияние C-way не означает O (N ^ 2). Используйте очередь приоритетов для слияния и все еще O (N lg N).

Вы также можете посмотреть кешировать забытые алгоритмы для сортировки.

Ответ 6

Почему вы не используете алгоритмы в http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850?

Они неплохие и тщательно объяснены.

Ответ 7

Вы сортируете или создаете новую копию? Если вы сортируете на месте, тогда отображение с отображением карты памяти IO обычно является хорошим вариантом. Просто сопоставьте весь файл и выполните сортировку слияния. ОС сохранит как можно больше файлов в памяти, и в зависимости от набора данных, как правило, минимизирует ваш IO.

Если вы пишете свой собственный алгоритм сортировки, один трюк должен обратить ваше направление после каждого прохода. Итак, если вы пройдете свой первый проход, вы начинаете от начала до конца, а затем переходите от конца к началу вашего второго прохода. Если вы разделите файлы на части A, B, C и D, то после сортировки C и D вы должны объединить C и D, а не вернуться к A и B. Причина, конечно, в вашей ОС будет страница частей файлов в память, и вы хотите использовать кеш как можно больше.