4551
правка
Внешние сортировка и перестановка: различия между версиями
Материал из WEGA
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 14:27, 20 мая 2023
, 20 мая 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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 = \ | Поскольку перестановка – это частный случай сортировки, то, следовательно, нижняя граница перестановки применима и к сортировке. В маловероятном случае, когда <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] вывели соответствующую нижнюю границу. | ||
