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

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

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

Модель

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

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

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

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

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

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

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

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

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

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

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

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

Запустите начальный этап сортировки фрагментов, как и раньше, чтобы создать отсортированные фрагменты размером 500×100 МБ.
Запустите первый проход слияния, объединяя фрагменты размером 25 × 100 МБ за раз, в результате чего будут отсортированы фрагменты размером 20 × 2,5 ГБ.
Запустите второй проход слияния, чтобы объединить отсортированные фрагменты размером 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). ^[4] При разумных предположениях по крайней мере 500 ГБ данных, хранящихся на жестком диске, можно отсортировать, используя 1 ГБ основной памяти, прежде чем третий проход станет выгодным, и во много раз больше данных можно отсортировать, прежде чем четвертый проход станет полезным. ^[5]

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Дональд Кнут , Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998 г., ISBN 0-201-89685-0 , Раздел 5.4: Внешняя сортировка, стр. 248–379.
^ Эллис Горовиц и Сартадж Сахни , Основы структур данных , Х. Фриман и компания, ISBN 0-7167-8042-9 .
^ Дональд Кнут , Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998 г., ISBN 0-201-89685-0 , Раздел 5.4: Внешняя сортировка, стр. 254 – и далее.
^ Один из способов увидеть это состоит в том, что при фиксированном объеме памяти (скажем, 1 ГБ) и минимальном размере чтения (скажем, 2 МБ) каждый проход слияния может объединить определенное количество прогонов (например, 500) в один, создавая Ситуация «разделяй и властвуй», аналогичная сортировке слиянием в памяти.
^ В качестве примера предположим, что 500 ГБ данных для сортировки, 1 ГБ буферной памяти и один диск со скоростью передачи 200 МБ/с и временем поиска 20 мс. На одной фазе слияния из 500 этапов будут использоваться буферы по 2 МБ каждый, и потребуется выполнить 250 тыс. операций поиска при чтении, а затем записи 500 ГБ. Он потратит 5000 секунд на поиск и 5000 секунд на передачу. Выполнение двух проходов слияния, как описано выше, почти устранит время поиска, но добавит дополнительные 5000 секунд времени передачи данных, так что это примерно точка безубыточности между двухпроходной и трехпроходной сортировкой.
^ Крис Ниберг, Мехул Шах, домашняя страница Sort Benchmark (ссылки на примеры параллельных сортировок)
^ Аггарвал, Алок; Виттер, Джеффри (1988). «Сложность ввода-вывода при сортировке и связанные с ней проблемы» (PDF) . Коммуникации АКМ . 31 (9): 1116–1127. дои : 10.1145/48529.48535 .
^ Дж. С. Виттер , Алгоритмы и структуры данных для внешней памяти , Серия «Основы и тенденции в теоретической информатике», теперь издатели, Ганновер, Массачусетс, 2008 г., ISBN 978-1-60198-106-6 .
^ Николас Аскитис, OzSort 2.0: Сортировка до 252 ГБ за копейки
^ Расмуссен и др., Triton Sort

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

[1] Дональд Кнут , Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998 г., ISBN 0-201-89685-0 , Раздел 5.4: Внешняя сортировка, стр. 248–379.

[2] Эллис Горовиц и Сартадж Сахни , Основы структур данных , Х. Фриман и компания, ISBN 0-7167-8042-9 .

[3] Дональд Кнут , Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998 г., ISBN 0-201-89685-0 , Раздел 5.4: Внешняя сортировка, стр. 254 – и далее.

[4] Один из способов увидеть это состоит в том, что при фиксированном объеме памяти (скажем, 1 ГБ) и минимальном размере чтения (скажем, 2 МБ) каждый проход слияния может объединить определенное количество прогонов (например, 500) в один, создавая Ситуация «разделяй и властвуй», аналогичная сортировке слиянием в памяти.

[5] В качестве примера предположим, что 500 ГБ данных для сортировки, 1 ГБ буферной памяти и один диск со скоростью передачи 200 МБ/с и временем поиска 20 мс. На одной фазе слияния из 500 этапов будут использоваться буферы по 2 МБ каждый, и потребуется выполнить 250 тыс. операций поиска при чтении, а затем записи 500 ГБ. Он потратит 5000 секунд на поиск и 5000 секунд на передачу. Выполнение двух проходов слияния, как описано выше, почти устранит время поиска, но добавит дополнительные 5000 секунд времени передачи данных, так что это примерно точка безубыточности между двухпроходной и трехпроходной сортировкой.

[6] Крис Ниберг, Мехул Шах, домашняя страница Sort Benchmark (ссылки на примеры параллельных сортировок)

[Aggarwal88-7] Аггарвал, Алок; Виттер, Джеффри (1988). «Сложность ввода-вывода при сортировке и связанные с ней проблемы» (PDF) . Коммуникации АКМ . 31 (9): 1116–1127. дои : 10.1145/48529.48535 .

[8] Дж. С. Виттер , Алгоритмы и структуры данных для внешней памяти , Серия «Основы и тенденции в теоретической информатике», теперь издатели, Ганновер, Массачусетс, 2008 г., ISBN 978-1-60198-106-6 .

[9] Николас Аскитис, OzSort 2.0: Сортировка до 252 ГБ за копейки

[10] Расмуссен и др., Triton Sort

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]