4511
правок
Внешние сортировка и перестановка: различия между версиями
Перейти к навигации
Перейти к поиску
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 21:27, 18 апреля 2023
, 18 апреля 2023→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Сортировка во внешней памяти == Постановка задачи == Нотаци…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Нотация. Основные свойства магнитных дисков и многодисковых систем можно отразить с помощью широко используемой модели с параллельными дисками (PDM), которая кратко представлена ниже в ее актуальной форме, разработанной Виттером и Шрайвер [16]: | Нотация. Основные свойства магнитных дисков и многодисковых систем можно отразить с помощью широко используемой ''модели с параллельными дисками'' (PDM), которая кратко представлена ниже в ее актуальной форме, разработанной Виттером и Шрайвер [16]: | ||
N – размер задачи (в единицах элементов данных); M – размер внутренней памяти (в единицах элементов данных); В – размер блока для поблочной передачи (в единицах элементов данных); D – количество независимых дисковых накопителей; P – количество | |||
где M < N и 1 | N – размер задачи (в единицах элементов данных); M – размер внутренней памяти (в единицах элементов данных); В – размер блока для поблочной передачи (в единицах элементов данных); D – количество независимых дисковых накопителей; P – количество процессоров; | ||
где <math>M < N</math> и <math>1 \le DB \le M/2</math>. Предполагается, что элементы данных имеют фиксированную длину. За одну операцию ввода-вывода каждый из D дисков может одновременно передать блок из B смежных элементов данных. (В оригинальной статье 1988 года [2] допускалось, что за одну операцию ввода-вывода с одного и того же диска могут поступать D блоков, что на практике нереально). Если <math>P \le D</math>, каждый из P процессоров может управлять примерно D/P дисками; если D < P, с каждым диском работают примерно P/D процессоров. Объем внутренней памяти составляет M/P на процессор; P процессоров соединены сетью межсоединений. | |||
Некоторые из перечисленных выше параметров PDM удобно указывать в единицах дисковых блоков, а не в единицах элементов данных; получаемые в результате формулы часто упрощаются. Будем обозначать строчными буквами | Некоторые из перечисленных выше параметров PDM удобно указывать в единицах дисковых блоков, а не в единицах элементов данных; получаемые в результате формулы часто упрощаются. Будем обозначать строчными буквами | ||
(1) <math>n = \frac{N}{B}, m = \frac{M}{B}, q = \frac{Q}{B}, z = \frac{Z}{B}</math> | |||
размер входных данных задачи, размер внутренней памяти, размер спецификации запроса и размер выходных данных запроса, соответственно, в единицах дисковых блоков. | размер входных данных задачи, размер внутренней памяти, размер спецификации запроса и размер выходных данных запроса, соответственно, в единицах дисковых блоков. | ||
| Строка 25: | Строка 29: | ||
Задача 1 (Внешняя сортировка) | '''Задача 1 (Внешняя сортировка)''' | ||
Дано: записи входных данных R0, R1, R2, . . изначально распределены чередующимся образом по D дискам в виде блоков, так что запись Ri находится в блоке bi/Bc, а блок ј хранится на диске j mod D. | Дано: записи входных данных R0, R1, R2, . . изначально распределены чередующимся образом по D дискам в виде блоков, так что запись Ri находится в блоке bi/Bc, а блок ј хранится на диске j mod D. | ||
| Строка 40: | Строка 44: | ||
Требуется: найти чередующееся представление переставленного (перестановочного) упорядочения Rcr^); Ra{1); Rcr{2) входных записей. | Требуется: найти чередующееся представление переставленного (перестановочного) упорядочения Rcr^); Ra{1); Rcr{2) входных записей. | ||
== Основные результаты == | == Основные результаты == | ||