4511
правок
Внешние сортировка и перестановка: различия между версиями
Перейти к навигации
Перейти к поиску
м
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 21:00, 18 мая 2023
, 18 мая 2023→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Нотация. Основные свойства магнитных дисков и многодисковых систем можно отразить с помощью широко используемой ''модели с параллельными дисками'' (PDM), которая кратко представлена ниже в ее актуальной форме, разработанной Виттером и Шрайвер [16]: | '''Нотация'''. Основные свойства магнитных дисков и многодисковых систем можно отразить с помощью широко используемой ''модели с параллельными дисками'' (PDM), которая кратко представлена ниже в ее актуальной форме, разработанной Виттером и Шрайвер [16]: | ||
N – размер задачи (в единицах элементов данных); M – размер внутренней памяти (в единицах элементов данных); В – размер блока для поблочной передачи (в единицах элементов данных); D – количество независимых дисковых накопителей; P – количество процессоров; | 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 процессоров соединены сетью межсоединений. | где <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 процессоров соединены сетью межсоединений. | ||
| Строка 36: | Строка 40: | ||
Операция перестановки представляет собой частный случай сортировки, в котором собственно перестановка, описывающая конечное расположение записей, задана явно и не требует выявления, например, путем сравнения ключей. | |||