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

Класс алгоритмов сортировки, способных обрабатывать огромные объемы данных

внешний алгоритм сортировки

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

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

Модель

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

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

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

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

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

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

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

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

Ограничение на однопроходное слияние заключается в том, что по мере увеличения количества фрагментов память будет делиться на большее количество буферов, поэтому каждый буфер будет меньше. В конце концов, чтения станут настолько маленькими, что больше времени будет тратиться на поиск на диске, чем на передачу данных. Типичный магнитный жесткий диск может иметь время доступа 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-кратное улучшение) более чем компенсирует удвоенное количество проходов слияния.

Вариации включают использование промежуточного носителя, такого как твердотельный диск , для некоторых этапов; быстрое временное хранилище не должно быть достаточно большим, чтобы вместить весь набор данных, просто должно быть существенно больше, чем доступная основная память. Повторяя пример выше с 1 ГБ временного хранилища SSD, первый проход может объединить 10×100 МБ отсортированных фрагментов, считанных из этого временного пространства, для записи 50x1 ГБ отсортированных фрагментов на HDD. Высокая пропускная способность и пропускная способность случайного чтения SSD помогают ускорить первый проход, а чтения HDD для второго прохода могут быть 2 МБ, достаточно большими, чтобы поиск не занимал большую часть времени чтения. SSD также могут использоваться в качестве буферов чтения на этапе слияния, позволяя выполнять меньше больших чтений (в этом примере 20 МБ чтения) с хранилища HDD. Учитывая более низкую стоимость емкости SSD по сравнению с ОЗУ, SSD могут быть экономичным инструментом для сортировки больших входных данных с очень ограниченной памятью.

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Дональд Кнут , Искусство программирования , Том 3: Сортировка и поиск , Второе издание. Addison-Wesley, 1998, ISBN  0-201-89685-0 , Раздел 5.4: Внешняя сортировка, стр. 248–379.
2. Эллис Горовиц и Сартадж Сахни , Основы структур данных , H. Freeman & Co., ISBN 0-7167-8042-9 . 
3. Дональд Кнут , Искусство программирования , Том 3: Сортировка и поиск , Второе издание. Addison-Wesley, 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 (ссылки на примеры параллельных сортировок)
7. Аггарвал, Алок; Виттер, Джеффри (1988). «Сложность ввода-вывода сортировки и связанные с ней проблемы» (PDF) . Сообщения ACM . 31 (9): 1116–1127. doi :10.1145/48529.48535.
8. Дж. С. Виттер , Алгоритмы и структуры данных для внешней памяти , серия «Основы и тенденции в теоретической информатике», теперь издательство, Ганновер, Массачусетс, 2008, ISBN 978-1-60198-106-6 . 
9. Николас Аскитис, OzSort 2.0: сортировка до 252 ГБ за копейки
10. Расмуссен и др., TritonSort

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

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