Внешняя сортировка

внешний алгоритм сортировки

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

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

Модель

См. также: Модель внешней памяти.

Алгоритмы внешней сортировки можно анализировать в модели внешней памяти . В этой модели кэш или внутренняя память размера M и неограниченная внешняя память разделены на блоки размера B , а время работы алгоритма определяется количеством передач памяти между внутренней и внешней памятью. Как и их аналоги , не обращающие внимания на кэш , асимптотически оптимальные алгоритмы внешней сортировки достигают времени работы (в нотации Big O ) $O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)$.

Внешняя сортировка слиянием

Одним из примеров внешней сортировки является внешний алгоритм сортировки слиянием , который использует алгоритм слияния K-way . Он сортирует фрагменты, каждый из которых помещается в ОЗУ, а затем объединяет отсортированные фрагменты вместе.

Алгоритм сначала сортирует M элементов за раз и помещает отсортированные списки обратно во внешнюю память. Это делает ${\tfrac {M}{B}}$-способ слияния этих отсортированных списков, рекурсивный, если недостаточно оперативной памяти для эффективного слияния за один проход. Во время прохода слияния B элементов из каждого отсортированного списка находятся во внутренней памяти, и минимум выводится повторно.

Например, для сортировки 900 мегабайт данных используется всего 100 мегабайт оперативной памяти:

1. Считайте 100 МБ данных в основной памяти и отсортируйте их обычным методом, например быстрой сортировкой .
2. Запишите отсортированные данные на диск.
3. Повторяйте шаги 1 и 2, пока все данные не будут разделены на отсортированные фрагменты по 100 МБ (существует 900 МБ / 100 МБ = 9 блоков), которые теперь необходимо объединить в один выходной файл.
4. Считайте первые 10 МБ (= 100 МБ / (9 фрагментов + 1)) каждого отсортированного фрагмента во входные буферы в основной памяти и выделите оставшиеся 10 МБ для выходного буфера. (На практике производительность можно повысить, если увеличить размер выходного буфера и немного уменьшить размер входного буфера.)
5. Выполните 9-стороннее слияние и сохраните результат в выходном буфере. Всякий раз, когда выходной буфер заполняется, записывайте его в окончательный отсортированный файл и очищайте его. Всякий раз, когда какой-либо из 9 входных буферов опустошается, заполняйте его следующими 10 МБ связанного с ним отсортированного фрагмента размером 100 МБ до тех пор, пока данные из фрагмента не перестанут быть доступны.

Проход слияния является ключом к тому, чтобы внешняя сортировка слиянием работала извне. Алгоритм слияния выполняет только один проход через каждый фрагмент, поэтому нет необходимости загружать все фрагменты одновременно; скорее, последовательные части фрагмента загружаются по мере необходимости. И пока считываемые блоки относительно велики (например, 10 МБ в этом примере), чтение может быть относительно эффективным даже на носителях с низкой производительностью произвольного чтения, таких как жесткие диски.

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

Дополнительные пропуска

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

Ограничением однопроходного слияния является то, что по мере увеличения количества фрагментов память будет делиться на большее количество буферов, поэтому каждый буфер становится меньше. В конце концов операции чтения становятся настолько малы, что больше времени тратится на поиск на диске, чем на передачу данных. Типичный магнитный жесткий диск может иметь время доступа 10 мс и скорость передачи данных 100 МБ/с, поэтому каждый поиск занимает столько же времени, сколько передача 1 МБ данных.

Таким образом, для сортировки, скажем, 50 ГБ в 100 МБ ОЗУ использование одного прохода слияния из 500 шагов неэффективно: мы можем прочитать только 100 МБ / 501 ≈ 200 КБ из каждого фрагмента одновременно, поэтому 5/6 из время диска тратится на поиск. Использование двух проходов слияния решает проблему. Тогда процесс сортировки может выглядеть так:

1. Запустите начальный этап сортировки фрагментов, как и раньше, чтобы создать отсортированные фрагменты размером 500×100 МБ.
2. Запустите первый проход слияния, объединяя фрагменты размером 25 × 100 МБ за раз, в результате чего будут отсортированы фрагменты размером 20 × 2,5 ГБ.
3. Запустите второй проход слияния, чтобы объединить отсортированные фрагменты размером 20 × 2,5 ГБ в один отсортированный результат размером 50 ГБ.

Хотя для этого требуется дополнительная передача данных, каждое чтение теперь занимает 4 МБ, поэтому на поиск тратится только 1/5 времени диска. Повышение эффективности передачи данных во время проходов слияния (от 16,6% до 80% — почти пятикратное улучшение) более чем компенсирует удвоенное количество проходов слияния.

промежуточного носителя, такого как твердотельный диск Варианты включают использование на некоторых этапах ; быстрое временное хранилище не обязательно должно быть достаточно большим, чтобы вместить весь набор данных, оно лишь существенно больше доступной основной памяти. Повторяя приведенный выше пример с 1 ГБ временного хранилища SSD, первый проход может объединить отсортированные фрагменты размером 10×100 МБ, считанные из этого временного пространства, для записи отсортированных фрагментов размером 50×1 ГБ на жесткий диск. Высокая пропускная способность и пропускная способность произвольного чтения твердотельных накопителей помогают ускорить первый проход, а объем операций чтения с жесткого диска для второго прохода может составлять 2 МБ, что достаточно велико, чтобы поиск не занимал большую часть времени чтения. Твердотельные накопители также можно использовать в качестве буферов чтения на этапе слияния, что позволяет сократить количество операций чтения большего размера (в данном примере — 20 МБ операций чтения) с жесткого диска. Учитывая более низкую стоимость емкости SSD по сравнению с оперативной памятью, твердотельные накопители могут быть экономичным инструментом для сортировки больших входных данных с очень ограниченной памятью.

Как и сортировка в памяти, эффективная внешняя сортировка требует времени O ( n log n ): экспоненциально растущие наборы данных требуют линейно увеличивающегося количества проходов, каждый из которых занимает время O (n). При разумных предположениях по крайней мере 500 ГБ данных, хранящихся на жестком диске, можно отсортировать, используя 1 ГБ основной памяти, прежде чем третий проход станет выгодным, и во много раз больше данных можно отсортировать, прежде чем четвертый проход станет полезным.

Размер основной памяти важен. Удвоение памяти, выделенной для сортировки, вдвое уменьшает количество фрагментов и количество операций чтения на каждый фрагмент, сокращая количество требуемых поисков примерно на три четверти. Соотношение оперативной памяти и дискового пространства на серверах часто позволяет удобно выполнять огромные сортировки на кластере машин. а не на одной машине с несколькими проходами. Носители с высокой производительностью произвольного чтения, такие как твердотельные накопители (SSD), также увеличивают объем, который можно отсортировать, прежде чем дополнительные проходы улучшат производительность.

Сортировка внешнего распределения

Сортировка внешнего распределения аналогична быстрой сортировке . Алгоритм находит приблизительно ${\tfrac {M}{B}}$ поворачивает и использует их для разделения N элементов на подмассивы примерно одинакового размера, каждый из которых меньше предыдущего, а затем выполняет рекурсию до тех пор, пока размеры подмассивов не станут меньше размера блока . Когда размер подмассивов меньше размера блока, сортировку можно выполнить быстро, поскольку все операции чтения и записи выполняются в кеше , а в модели внешней памяти требуется $O(1)$ операции.

Однако найти именно ${\tfrac {M}{B}}$ повороты не будут достаточно быстрыми, чтобы сделать сортировку внешнего распределения асимптотически оптимальной . Вместо этого мы обнаруживаем немного меньше поворотов. Чтобы найти эти опорные точки, алгоритм разбивает N входных элементов на ${\tfrac {N}{M}}$ куски и принимает каждый ${\sqrt {\tfrac {M}{16B}}}$ элементов и рекурсивно использует алгоритм медианы медиан для поиска ${\sqrt {\tfrac {M}{B}}}$ шарниры.

Существует двойственность или фундаментальное сходство между алгоритмами, основанными на слиянии и распределении.

Производительность

Тест сортировки, созданный ученым-компьютерщиком Джимом Греем , сравнивает внешние алгоритмы сортировки, реализованные с использованием точно настроенного аппаратного и программного обеспечения. В успешных реализациях используется несколько методов:

• Использование параллелизма
  • Несколько дисковых накопителей можно использовать параллельно, чтобы улучшить скорость последовательного чтения и записи. Это может быть очень экономически эффективным улучшением: победитель Sort Benchmark в категории «Penny Sort», ориентированный на затраты, использует шесть жестких дисков в машине среднего класса.
  • Программное обеспечение для сортировки может использовать несколько потоков для ускорения процесса на современных многоядерных компьютерах.
  • Программное обеспечение может использовать асинхронный ввод-вывод , чтобы можно было сортировать или объединять одну серию данных, в то время как другие прогоны считываются с диска или записываются на диск.
  • Несколько машин, соединенных быстрыми сетевыми соединениями, могут параллельно сортировать часть огромного набора данных.
• Увеличение аппаратной скорости
  • Использование большего объема оперативной памяти для сортировки может уменьшить количество операций поиска на диске и избежать необходимости выполнения дополнительных проходов.
  • Быстрая внешняя память, такая как твердотельные накопители, может ускорить сортировку либо в том случае, если данные достаточно малы, чтобы полностью поместиться на твердотельные накопители, либо, что реже, для ускорения сортировки фрагментов размером с твердотельный накопитель при трехпроходной сортировке.
  • многие На максимальную скорость сортировки оборудования могут влиять другие факторы: скорость процессора и количество ядер, задержка доступа к ОЗУ, пропускная способность ввода/вывода, скорость чтения/записи диска, время поиска на диске и другие. «Балансировка» оборудования для минимизации узких мест является важной частью разработки эффективной системы сортировки.
  • Экономическая эффективность, а также абсолютная скорость могут иметь решающее значение, особенно в кластерных средах, где более низкие затраты на узлы позволяют приобретать больше узлов.
• Увеличение скорости программного обеспечения
  • Некоторые участники Sort Benchmark используют вариант поразрядной сортировки на первом этапе сортировки: они разделяют данные в одну из многих «корзин» на основе начала их значения. Сортировка данных Benchmark осуществляется случайным образом и особенно хорошо подходит для такой оптимизации.
  • Сжатие входных, промежуточных файлов и выходных данных может сократить время, затрачиваемое на ввод-вывод, но не допускается в тесте сортировки.
  • Поскольку Sort Benchmark сортирует длинные (100-байтовые) записи с использованием коротких (10-байтовых) ключей, программное обеспечение для сортировки иногда переупорядочивает ключи отдельно от значений, чтобы уменьшить объем операций ввода-вывода в памяти.

См. также

• Объединение сортировки мэйнфреймов
• Алгоритм внешней памяти
• Воронкообразная сортировка
• Сортировка распределения без учета кэша

Внешние ссылки

• STXXL, набор инструментов для алгоритмов, включающий внешнюю сортировку слиянием.
• Пример внешней сортировки слиянием
• Реализация слияния K-Way
• Сортировка внешней памяти в Java
• Пример реализации пеннисортировки с использованием Judy Arrays
• Сортировка