4551
правка
Внешние сортировка и перестановка: различия между версиями
Материал из WEGA
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 16:14, 19 апреля 2023
, 19 апреля 2023→Обработка дубликатов: пакетная сортировка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 115: | Строка 115: | ||
'''Обработка дубликатов: пакетная сортировка''' | |||
Для ''удаления дубликатов'', когда среди N элементов имеется в общей сложности K различных элементов, Арге и др. [3] используют модификацию сортировки слиянием для решения этой задачи за <math>O(n \; max \{ 1,log_m (K/B) \} )</math> операций ввода-вывода, что является оптимальным в модели сравнения [3]. Когда во время слияния дубликаты группируются вместе, они заменяются единственной копией элемента и подсчетом числа его вхождений. Этот алгоритм можно использовать для сортировки файла, предполагая, что группа одинаковых элементов может быть представлена одним элементом и подсчитанным числом появлений. | |||
Более сложный случай сортировки, называемый ''пакетной сортировкой'', имеет место, когда среди N элементов есть K различных ключевых значений, но все элементы содержат различную вторичную информацию, которая должна сохраняться, и поэтому не могут быть объединены с помощью подсчета. Матиас и др. разработали оптимальные алгоритмы сортировки распределением для пакетной сортировки, используя | |||
операций ввода-вывода и доказав соответствие нижней границы. Они также показали, как выполнять пакетную сортировку (и сортировку вообще) на месте (т. е. без дополнительного дискового пространства). | (6) <math>O(n \; max \{ 1,log_m \; min \{ K, n \} \} )</math> | ||
операций ввода-вывода и доказав соответствие нижней границы. Они также показали, как выполнять пакетную сортировку (и сортировку вообще) ''на месте'' (т. е. без использования дополнительного дискового пространства). | |||
'''Перестановка и транспонирование''' | '''Перестановка и транспонирование''' | ||
Перестановка представляет собой | Перестановка представляет собой частный случай сортировки, в котором ключевые значения N элементов данных образуют перестановку {1, 2, ... , N}. Граница ввода-вывода (3) для перестановки может быть реализована одним из оптимальных алгоритмов сортировки, за исключением крайнего случая B log m = o (log n), когда быстрее переместить элементы данных по одному неблокирующим способом. Метод перемещения элементов по одному тривиален, если D = 1, но при использовании нескольких дисков могут возникать узкие места на отдельных дисках; одним из решений для выполнения перестановки за O(N/D) операций ввода-вывода является применение рандомизированных стратегий балансировки из работы [16]. | ||
Транспонирование матрицы может быть таким же трудным, как и перестановка общего вида, когда B относительно велико (скажем, 1/2M) и N составляет O( | Транспонирование матрицы может быть таким же трудным, как и перестановка общего вида, когда B относительно велико (скажем, 1/2M) и N составляет <math>O(M^2)</math>; однако при меньших значениях B специальная структура перестановки упрощает процесс транспонирования. В частности, матрица может быть разбита на квадратные подматрицы из <math>B^2</math> элементов так, чтобы каждая подматрица содержала B блоков матрицы в порядке возрастания строк, а также B блоков матрицы в порядке возрастания столбцов. Таким образом, если <math>B^2 < M</math>, транспонирование может быть произведено простой однопроходной операцией путем транспонирования по одной подматрице во внутренней памяти. | ||
| Строка 143: | Строка 144: | ||
== Нижние границы для операций ввода-вывода == | |||
Следующее доказательство нижней границы перестановки (3) теоремы 2 принадлежит Аггарвалу и Виттеру [ ]. Идея доказательства состоит в том, чтобы для каждого t > 0 вычислить число различных упорядочений, которые реализуются последовательностями из t операций ввода-вывода. Значение t, при котором число различных упорядочений впервые превышает N!/2, является нижней границей среднего числа операций ввода-вывода (и, следовательно, числа таких операций в наихудшем случае), необходимых для выполнения перестановки. | Следующее доказательство нижней границы перестановки (3) теоремы 2 принадлежит Аггарвалу и Виттеру [ ]. Идея доказательства состоит в том, чтобы для каждого t > 0 вычислить число различных упорядочений, которые реализуются последовательностями из t операций ввода-вывода. Значение t, при котором число различных упорядочений впервые превышает N!/2, является нижней границей среднего числа операций ввода-вывода (и, следовательно, числа таких операций в наихудшем случае), необходимых для выполнения перестановки. | ||
