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

Question

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

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

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

Answer 1

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

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

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

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

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

Кроме того, я, конечно, не придумал этого - я, вероятно, впервые прочитал об этом в Кнуте, но, возможно, в Алгоритмы + Структуры данных = Программы (Никлаус Вирт) - оба обсуждают это. Кнут приписывает первую публикацию метода «Х. Сьюарду» в своей магистерской диссертации в Массачусетском технологическом институте в 1954 году. Если у вас есть второе издание Кнута, оно находится на странице 254 тома 3. У меня нет копии третьего издание, поэтому у меня нет номера страницы для этого.

Answer 2

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

«Использовать команду unix sort »

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

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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

Answer 7

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

Они довольно хороши и тщательно объяснены.