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

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

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

Модель

Алгоритмы внешней сортировки можно анализировать в модели внешней памяти . В этой модели кэш или внутренняя память размера $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]