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

Перейти к навигации Перейти к поиску
Строка 126: Строка 126:




Более сложный случай сортировки, называемый ''пакетной сортировкой'', имеет место, когда среди N элементов есть K различных ключевых значений, но все элементы содержат различную вторичную информацию, которая должна сохраняться, и поэтому не могут быть объединены с помощью подсчета. Матиас и др. разработали оптимальные алгоритмы сортировки распределением для пакетной сортировки, используя
Более сложный случай сортировки, называемый ''пакетной сортировкой'', имеет место, когда среди N элементов есть K различных ключевых значений, но все элементы содержат различную вторичную информацию, которая должна сохраняться, и поэтому не могут быть объединены с помощью подсчета. Матиас и др. [10] разработали оптимальные алгоритмы сортировки распределением для пакетной сортировки, используя


(6) <math>O(n \; max \{ 1,log_m \; min \{ K, n \} \} )</math>
(6) <math>O(n \; max \{ 1,log_m \; min \{ K, n \} \} )</math>
Строка 156: Строка 156:
Предположив на данный момент, что имеется только один диск, D = 1, рассмотрим, как может измениться количество реализуемых упорядочений в результате ввода-вывода. С точки зрения увеличения числа реализуемых упорядочений, эффект от чтения дискового блока значительно больше, чем от его записи, поэтому достаточно рассмотреть только эффект от операций чтения. Во время операции чтения в блоке чтения имеется не более B элементов данных, и они могут быть размещены среди М элементов во внутренней памяти не более чем <math>\binom{M}{B}</math> способами, поэтому число реализуемых упорядочений увеличивается в <math>\binom{M}{B}</math> раз. Если блок никогда ранее не находился во внутренней памяти, то число реализуемых упорядочений увеличивается на дополнительный коэффициент В!, поскольку элементы в блоке могут быть переставлены между собой. (Этот дополнительный вклад B! может иметь место только один раз для каждого из N/B исходных блоков). Существует не более <math>n + t \le N \; log \; N</math> способов выбрать, какой дисковый блок участвует в t-й операции ввода-вывода (при произвольном объеме дискового пространства). Следовательно, число различных упорядочений, которые могут быть реализованы всеми возможными последовательностями t операций ввода-вывода, не превышает
Предположив на данный момент, что имеется только один диск, D = 1, рассмотрим, как может измениться количество реализуемых упорядочений в результате ввода-вывода. С точки зрения увеличения числа реализуемых упорядочений, эффект от чтения дискового блока значительно больше, чем от его записи, поэтому достаточно рассмотреть только эффект от операций чтения. Во время операции чтения в блоке чтения имеется не более B элементов данных, и они могут быть размещены среди М элементов во внутренней памяти не более чем <math>\binom{M}{B}</math> способами, поэтому число реализуемых упорядочений увеличивается в <math>\binom{M}{B}</math> раз. Если блок никогда ранее не находился во внутренней памяти, то число реализуемых упорядочений увеличивается на дополнительный коэффициент В!, поскольку элементы в блоке могут быть переставлены между собой. (Этот дополнительный вклад B! может иметь место только один раз для каждого из N/B исходных блоков). Существует не более <math>n + t \le N \; log \; N</math> способов выбрать, какой дисковый блок участвует в t-й операции ввода-вывода (при произвольном объеме дискового пространства). Следовательно, число различных упорядочений, которые могут быть реализованы всеми возможными последовательностями t операций ввода-вывода, не превышает


(7) <math>(B!)^{N/B} \bigg( N (log \; N) \binom{M}{B} \bigg).</math>
(7) <math>(B!)^{N/B} \bigg( N (log \; N) \binom{M}{B} \bigg)^t.</math>




Строка 169: Строка 169:




Поскольку перестановка – это частный случай сортировки, то, следовательно, нижняя граница перестановки применима и к сортировке. В маловероятном случае, когда <math>В \; log \; m = o(log \; n)</math>, нижняя граница перестановки составляет только <math>\Omega(N/D)</math>, и в этом случае для получения полной нижней границы (2) теоремы 1 [2] необходимо использовать модель сравнения. В типичном случае, когда <math>В \; log \; m = \omega (log \; N)</math>, модель сравнения для доказательства нижней границы сортировки не нужна; сложность сортировки в этом случае возникает не из-за определения порядка данных, а из-за перестановки (или маршрутизации) данных.
Поскольку перестановка – это частный случай сортировки, то, следовательно, нижняя граница перестановки применима и к сортировке. В маловероятном случае, когда <math>В \; log \; m = o(log \; n)</math>, нижняя граница перестановки составляет только <math>\Omega(N/D)</math>, и в этом случае для получения полной нижней границы (2) теоремы 1 [2] необходимо использовать модель сравнения. В типичном случае, когда <math>В \; log \; m = \Omega (log \; N)</math>, модель сравнения для доказательства нижней границы сортировки не нужна; сложность сортировки в этом случае возникает не из-за определения порядка данных, а из-за перестановки (или маршрутизации) данных.




Строка 175: Строка 175:




Для задачи сортировки пакетной, в которой N элементов имеют в общей сложности K различных ключевых значений (но вторичная информация каждого элемента отлична от других), Матиас и др. [10] вывели соответствующую нижнюю границу.
Для задачи пакетной сортировки, в которой N элементов принимают в общей сложности K различных ключевых значений (но вторичная информация каждого элемента отлична от других), Матиас и др. [10] вывели соответствующую нижнюю границу.




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