4511
правок
Внешние сортировка и перестановка: различия между версиями
Перейти к навигации
Перейти к поиску
м
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 15:38, 19 апреля 2023
, 19 апреля 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
Теорема 2 [2]. Количество операций ввода-вывода, необходимых для перестановки N элементов данных с использованием D дисков в среднем и наихудшем случаях, составляет | '''Теорема 2 [2]. Количество операций ввода-вывода, необходимых для перестановки N элементов данных с использованием D дисков в среднем и наихудшем случаях, составляет''' | ||
(3) <math>\Theta \bigg( min \bigg\{ \frac{N}{D}, Sort(N) \bigg\} \bigg).</math> | (3) <math>\Theta \bigg( min \bigg\{ \frac{N}{D}, Sort(N) \bigg\} \bigg).</math> | ||
| Строка 60: | Строка 60: | ||
Теорема 3 [2]. При наличии D дисков количество операций ввода-вывода, необходимых для транспонирования матрицы p x q из развертывания по строкам на развертывание по столбцам, равно | '''Теорема 3 [2]. При наличии D дисков количество операций ввода-вывода, необходимых для транспонирования матрицы p x q из развертывания по строкам на развертывание по столбцам, равно''' | ||
(4) | (4)<math>\Theta \bigg( \frac{n}{D} log_m min \{ M, p, q, n \} \bigg),</math> | ||
где N = pq и n = N/B. | где N = pq и n = N/B. | ||
Транспонирование матриц является частным случаем более общего класса перестановок, называемых перестановками типа | Транспонирование матриц является частным случаем более общего класса перестановок, называемых перестановками типа «''перестановка битов и дополнение''» (bit-permute/complement, BPC), которые, в свою очередь, являются подмножеством класса перестановок типа «''перемножение битовых матриц и дополнение''» (bit-matrix-multiply/complement, BMMC). BMMC-перестановки определяются неособенной матрицей A размера log N x log N, содержащей только нули и единицы, и вектором длины log N с такими же элементами. Элемент с двоичным адресом x отображается перестановкой на двоичный адрес, заданный Ax ф c, где В обозначает поразрядное исключающее «ИЛИ». BPC-перестановки являются частным случаем BMMC-перестановок, в котором A является матрицей перестановок, то есть каждая строка и каждый столбец A содержат по одному значению 1. BPC-перестановки включают в себя транспонирование матрицы, бит-реверсивную перестановку (которая возникает при быстром преобразовании Фурье), обращение векторов, перестановку элементов гиперкуба и переблокировку матрицы. Кормен и коллеги [6] характеризуют оптимальное число операций ввода-вывода, необходимое для выполнения любой заданной BMMC-перестановки, исключительно как функцию от соответствующей матрицы A, а дакже дают оптимальный алгоритм ее реализации. | ||
| Строка 101: | Строка 101: | ||
== Сортировка слиянием == | |||
Парадигма слияния в некотором смысле ортогональна парадигме распределения из предыдущего раздела. Типичный алгоритм сортировки слиянием работает следующим образом [ ]: на этапе «формирования прогонов» сканируется n блоков данных, по одной загрузке в память за раз; каждая загрузка в память сортируется в один «прогон», который затем выводится на серию полос на дисках. По завершении этапа формирования прогонов имеется N/M = n/m (отсортированных) прогонов, каждый из которых разбит на полосы на дисках. (При реализации алгоритма на практике можно использовать выбор с замещением для получения прогонов из 2M элементов данных в среднем при M "S [9]). После того, как начальные прогоны сформированы, начинается этап слияния. При каждом проходе фазы слияния за один раз объединяется R прогонов. Для каждого слияния R прогонов сканируются, и их элементы объединяются в онлайновом режиме по мере их прохождения через внутреннюю память. Для перекрытия операций ввода-вывода и вычислений используется двойная буферизация. За один раз может быть объединено не более R = 0{m) прогонов, а итоговое число проходов составляет O(logm n). | Парадигма слияния в некотором смысле ортогональна парадигме распределения из предыдущего раздела. Типичный алгоритм сортировки слиянием работает следующим образом [ ]: на этапе «формирования прогонов» сканируется n блоков данных, по одной загрузке в память за раз; каждая загрузка в память сортируется в один «прогон», который затем выводится на серию полос на дисках. По завершении этапа формирования прогонов имеется N/M = n/m (отсортированных) прогонов, каждый из которых разбит на полосы на дисках. (При реализации алгоритма на практике можно использовать выбор с замещением для получения прогонов из 2M элементов данных в среднем при M "S [9]). После того, как начальные прогоны сформированы, начинается этап слияния. При каждом проходе фазы слияния за один раз объединяется R прогонов. Для каждого слияния R прогонов сканируются, и их элементы объединяются в онлайновом режиме по мере их прохождения через внутреннюю память. Для перекрытия операций ввода-вывода и вычислений используется двойная буферизация. За один раз может быть объединено не более R = 0{m) прогонов, а итоговое число проходов составляет O(logm n). | ||