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

Перейти к навигации Перейти к поиску
мНет описания правки
Строка 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:




Перестановка представляет собой частный случай сортировки, в котором перемещение, описывающее конечное расположение записей, задано явно и не требует выявления, например, путем сравнения ключей.
Операция перестановки представляет собой частный случай сортировки, в котором собственно перестановка, описывающая конечное расположение записей, задана явно и не требует выявления, например, путем сравнения ключей.
   
   


Источник — http://pco.iis.nsk.su/wega/index.php/Внешние_сортировка_и_перестановка