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

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

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

Модель [ править ]

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

Внешняя сортировка слиянием [ править ]

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

Алгоритм сначала сортирует 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 МБ до тех пор, пока данные из этого фрагмента не станут доступны. Это ключевой шаг, который заставляет внешнюю сортировку слиянием работать извне - поскольку алгоритм слияния выполняет только один проход последовательно через каждый из фрагментов, каждый фрагмент не нужно загружать полностью; скорее, при необходимости могут быть загружены последовательные части блока.

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

Дополнительные проходы [ править ]

Предыдущий пример представляет собой двухпроходную сортировку: сначала сортировка, затем слияние. Сортировка заканчивается одним 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 ГБ основной памяти, прежде чем третий проход станет предпочтительным, и во много раз больше данных можно отсортировать до того, как четвертый проход станет полезным. ^[4] Носители с малым временем поиска, такие как твердотельные накопители (SSD), также увеличивают объем, который может быть отсортирован до того, как дополнительные проходы улучшат производительность.

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

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

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

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

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

Производительность [ править ]

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

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

Ссылки [ править ]

См. Также [ править ]

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

Внешние ссылки [ править ]

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