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

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

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

Модель

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

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

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

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

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

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

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

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

Предыдущий пример представляет собой двухпроходную сортировку: сначала сортировка, затем слияние. Сортировка заканчивается одним k- way слиянием, а не серией двусторонних проходов слияния, как при типичной сортировке слиянием в памяти. Это связано с тем, что каждый проход слияния считывает и записывает каждое значение с диска и на диск, поэтому уменьшение количества проходов более чем компенсирует дополнительные затраты на слияние 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% - почти 5-кратное улучшение) более чем компенсирует удвоенное количество проходов слияния.

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

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

Сортировка по внешнему распределению

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

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

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

Представление

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

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

Смотрите также

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

Рекомендации

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

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