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

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

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

• 1 Модель
• 2 Внешняя сортировка слиянием
  • 2.1 Дополнительные проходы
• 3 Внешняя сортировка распределения
• 4 Производительность
• 5 Ссылки
• 6 См. Также
• 7 Внешняя ссылки

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

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

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

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

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

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

Дополнительные проходы

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

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

1. Выполните начальный этап сортировки фрагментов, как и раньше.
2. Выполните первый проход слияния, объединяя 25 фрагментов за раз, в результате чего получается 20 отсортированных фрагментов большего размера.
3. Выполните второй проход слияния, чтобы объединить 20 больших отсортированных фрагментов.

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

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

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

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

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

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

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

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

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