Внешние сортировка и перестановка: различия между версиями

Перейти к навигации Перейти к поиску
Строка 98: Строка 98:
Метод рандомизированного зацикливания или связанные с ним методы сортировки слиянием, рассмотренные в конце раздела «Сортировка слиянием», являются предпочтительными для сортировки с использованием параллельных дисков. Преимущество алгоритмов сортировки распределением над подходами на основе слияния, представленными в разделе «Сортировка слиянием», заключается в том, что они обычно лучше используют нижние уровни кэша в иерархии памяти реальных систем, о чем можно судить по анализу алгоритмов сортировки распределением и сортировки слиянием на моделях иерархической памяти.
Метод рандомизированного зацикливания или связанные с ним методы сортировки слиянием, рассмотренные в конце раздела «Сортировка слиянием», являются предпочтительными для сортировки с использованием параллельных дисков. Преимущество алгоритмов сортировки распределением над подходами на основе слияния, представленными в разделе «Сортировка слиянием», заключается в том, что они обычно лучше используют нижние уровни кэша в иерархии памяти реальных систем, о чем можно судить по анализу алгоритмов сортировки распределением и сортировки слиянием на моделях иерархической памяти.


== Сортировка слиянием ==
'''Сортировка слиянием'''


Парадигма слияния в некотором смысле ортогональна парадигме распределения из предыдущего раздела. Типичный алгоритм сортировки слиянием работает следующим образом [ ]: на этапе «формирования прогонов» сканируется n блоков данных, по одной загрузке в память за раз; каждая загрузка в память сортируется в один «прогон», который затем выводится на серию полос на дисках. По завершении этапа формирования прогонов имеется N/M = n/m (отсортированных) прогонов, каждый из которых разбит на полосы на дисках. (При реализации алгоритма на практике можно использовать выбор с замещением для получения прогонов из 2M элементов данных в среднем при M "S [9]). После того, как начальные прогоны сформированы, начинается этап слияния. При каждом проходе фазы слияния за один раз объединяется R прогонов. Для каждого слияния R прогонов сканируются, и их элементы объединяются в онлайновом режиме по мере их прохождения через внутреннюю память. Для перекрытия операций ввода-вывода и вычислений используется двойная буферизация. За один раз может быть объединено не более R = 0{m) прогонов, а итоговое число проходов составляет O(logm n).
Парадигма ''слияния'' в некотором смысле ортогональна парадигме распределения из предыдущего раздела. Типичный алгоритм сортировки слиянием работает следующим образом [9]: на этапе «формирования прогонов» сканируется n блоков данных, по одной загрузке в память за раз; каждая загрузка в память сортируется в один «прогон», который затем выводится на серию полос на дисках. По завершении этапа формирования прогонов имеется N/M = n/m (отсортированных) прогонов, каждый из которых разбит на полосы на дисках. (При реализации алгоритма на практике можно использовать выбор с замещением для получения прогонов из 2M элементов данных в среднем при M >> B [9]). После того, как начальные прогоны сформированы, начинается этап слияния. При каждом проходе фазы слияния за один раз объединяется R прогонов. Для каждого слияния R прогонов сканируются, и их элементы объединяются в онлайновом режиме по мере их прохождения через внутреннюю память. Для перекрытия операций ввода-вывода и вычислений используется двойная буферизация. За один раз может быть объединено не более <math>R = \Theta(m)</math> прогонов, а итоговое число проходов составляет <math>O(log_m \; n)</math>.




Для достижения оптимальной границы сортировки (2) каждый проход слияния должен выполняться за O(n/D) операций ввода-вывода, что легко сделать для случая с использованием одного диска. В более общем случае с несколькими дисками каждая операция параллельного чтения во время процесса слияния должна в среднем выдать следующие 0{D) блоков, необходимых для слияния. Задача состоит в том, чтобы обеспечить размещение этих блоков на разных дисках так, чтобы они могли быть прочитаны за одну операцию ввода-вывода (или небольшое постоянное число таких операций). Сложность же заключается в том, что подлежащие слиянию прогоны были сформированы во время предыдущего прохода слияния. Их блоки были записаны на диски в предыдущем проходе без знания того, как они будут взаимодействовать с другими прогонами в последующих слияниях.
Для достижения оптимальной границы сортировки (2) каждый проход слияния должен выполняться за O(n/D) операций ввода-вывода, что легко сделать для случая с использованием одного диска. В более общем случае с несколькими дисками каждая операция параллельного чтения во время процесса слияния должна в среднем выдать следующие <math>\Theta(D)</math> блоков, необходимых для слияния. Задача состоит в том, чтобы обеспечить размещение этих блоков на разных дисках так, чтобы они могли быть прочитаны за одну операцию ввода-вывода (или небольшое постоянное число таких операций). Сложность же заключается в том, что подлежащие слиянию прогоны были сформированы во время предыдущего прохода слияния. Их блоки были записаны на диски в предыдущем проходе без знания того, как они будут взаимодействовать с другими прогонами в последующих слияниях.




Метод жадной сортировки (Greed Sort) Нодина и Виттера [12] был первым оптимальным детерминированным EM-алгоритмом для сортировки с использованием нескольких дисков. Он работает путем ослабления процесса слияния с последним проходом для фиксации слияния. Аггарвал и Плакстон [ ] разработали оптимальный детерминированный метод сортировки слиянием на основе алгоритма параллельной сортировки гиперкуба Sharesort. Чтобы гарантировать равномерное распределение во время слияния, они используют две высокоуровневые схемы слияния, в которых планирование почти не учитывается. Как и Greed Sort, алгоритм Sharesort теоретически оптимален (т. е. отличается от оптимального не более чем на константный коэффициент), но этот константный коэффициент больше, чем у методов сортировки распределением.
Метод жадной сортировки (Greed Sort) Нодина и Виттера [12] был первым оптимальным детерминированным EM-алгоритмом для сортировки с использованием нескольких дисков. Он работает путем ослабления процесса слияния с последним проходом для фиксации слияния. Аггарвал и Плакстон [1] разработали оптимальный детерминированный метод сортировки слиянием на основе алгоритма параллельной сортировки гиперкуба Sharesort. Чтобы гарантировать равномерное распределение во время слияния, они используют две высокоуровневые схемы слияния, в которых планирование почти не учитывается. Как и Greed Sort, алгоритм Sharesort теоретически оптимален (т. е. отличается от оптимального не более чем на константный коэффициент), но этот константный коэффициент больше, чем у методов сортировки распределением.
Один из наиболее практичных методов сортировки основан на простом алгоритме рандомизированной сортировки слиянием (SRM) Барве и коллег [5], который Кнут назвал [9] «рандомизированным чередованием». Каждый прогон чередуется полосами по дискам, но со случайной начальной точки (это единственное место в алгоритме, где используется случайность). В процессе слияния следующий требуемый блок с каждого диска считывается в память, а если места недостаточно, то наименее нужные блоки «сбрасываются» (без применения каких-либо операций ввода-вывода), чтобы освободить место.




Для дальнейшего улучшения эффективности сортировки слиянием требуется более тщательное составление расписания предварительной выборки для прогонов. Барве и др. [ ], Каллахалла и Варман [8], Шах и коллеги [13], а также другие исследователи разработали конкурентоспособные и оптимальные методы предварительной выборки блоков в параллельных системах ввода-вывода. Хатчинсон и др. [7] продемонстрировали мощную двойственность между параллельной записью и параллельной предварительной выборкой, которая дает простой способ вычисления оптимальных расписаний предварительной выборки и кэширования при использовании нескольких дисков. Более того, они показали, что такая же двойственность существует между распределением и слиянием, а также использовали это открытие для получения доказательно оптимальной и очень практичной сортировки слиянием с использованием параллельных дисков. Вместо того, чтобы использовать случайные начальные точки и циклическое упорядочивание полос, как в алгоритме SRM, Хатчинсон и др. [ ] упорядочивают полосы независимо для каждого прогона, основываясь на стратегии случайного зацикливания, рассмотренной в разделе «Сортировка распределением».
Один из наиболее практичных методов сортировки основан на алгоритме ''простой рандомизированной сортировки слиянием'' (SRM) Барве и коллег [5], который Кнут назвал [9] «рандомизированным чередованием». Каждый прогон чередуется полосами по дискам, но со случайной начальной точки (это единственное место в алгоритме, где используется случайность). В процессе слияния следующий требуемый блок с каждого диска считывается в память, а если места недостаточно, то наименее нужные блоки «сбрасываются» (без применения каких-либо операций ввода-вывода), чтобы освободить место.




'''Обработка дубликатов: пакетная сортировка'''
Для дальнейшего улучшения эффективности сортировки слиянием требуется более тщательное составление расписания предварительной выборки для прогонов. Барве и др. [4], Каллахалла и Варман [8], Шах и коллеги [13], а также другие исследователи разработали конкурентоспособные и оптимальные методы предварительной выборки блоков в параллельных системах ввода-вывода. Хатчинсон и др. [7] продемонстрировали мощную двойственность между параллельной записью и параллельной предварительной выборкой, которая дает простой способ вычисления оптимальных расписаний предварительной выборки и кэширования при использовании нескольких дисков. Более того, они показали, что такая же двойственность существует между распределением и слиянием, а также использовали это открытие для получения доказательно оптимальной и очень практичной сортировки слиянием с использованием параллельных дисков. Вместо того, чтобы использовать случайные начальные точки и циклическое упорядочивание полос, как в алгоритме SRM, Хатчинсон и др. [7] упорядочивают полосы независимо для каждого прогона, основываясь на стратегии случайного зацикливания, рассмотренной в разделе «Сортировка распределением».
 
 
== Обработка дубликатов: пакетная сортировка ==


Для удаления дубликатов, когда среди N элементов имеется в общей сложности K различных элементов, Арге и др. [3] используют модификацию сортировки слиянием для решения этой задачи за 0(nmax{l,logm(.Kyfi)}) операций ввода-вывода, что является оптимальным в модели сравнения [3]. Когда во время слияния дубликаты группируются вместе, они заменяются единственной копией элемента и подсчетом числа его вхождений. Этот алгоритм можно использовать для сортировки файла, предполагая, что группа одинаковых элементов может быть представлена одним элементом и подсчитанным числом появлений.
Для удаления дубликатов, когда среди N элементов имеется в общей сложности K различных элементов, Арге и др. [3] используют модификацию сортировки слиянием для решения этой задачи за 0(nmax{l,logm(.Kyfi)}) операций ввода-вывода, что является оптимальным в модели сравнения [3]. Когда во время слияния дубликаты группируются вместе, они заменяются единственной копией элемента и подсчетом числа его вхождений. Этот алгоритм можно использовать для сортировки файла, предполагая, что группа одинаковых элементов может быть представлена одним элементом и подсчитанным числом появлений.
Источник — http://pco.iis.nsk.su/wega/index.php/Внешние_сортировка_и_перестановка