4430
правок
Внешние сортировка и перестановка: различия между версиями
Перейти к навигации
Перейти к поиску
м
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 13:09, 18 мая 2023
, 18 мая 2023→Нижние границы для операций ввода-вывода
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 144: | Строка 144: | ||
Алгоритмы для БПФ быстрее и проще, чем для сортировки, поскольку вычисления неадаптивны по своей природе и, таким образом, схема коммуникаций фиксирована заранее [16]. | Алгоритмы для БПФ быстрее и проще, чем для сортировки, поскольку вычисления неадаптивны по своей природе и, таким образом, схема коммуникаций фиксирована заранее [16]. | ||
'''Нижние границы для операций ввода-вывода''' | |||
Следующее доказательство нижней границы перестановки (3) теоремы 2 принадлежит Аггарвалу и Виттеру [2]. Идея доказательства состоит в том, чтобы для каждого <math>t \ge 0</math> вычислить число различных упорядочений, которые реализуются последовательностями из t операций ввода-вывода. Значение t, при котором число различных упорядочений впервые превышает N!/2, является нижней границей среднего числа операций ввода-вывода (и, следовательно, числа таких операций в наихудшем случае), необходимых для выполнения перестановки. | Следующее доказательство нижней границы перестановки (3) теоремы 2 принадлежит Аггарвалу и Виттеру [2]. Идея доказательства состоит в том, чтобы для каждого <math>t \ge 0</math> вычислить число различных упорядочений, которые реализуются последовательностями из t операций ввода-вывода. Значение t, при котором число различных упорядочений впервые превышает N!/2, является нижней границей среднего числа операций ввода-вывода (и, следовательно, числа таких операций в наихудшем случае), необходимых для выполнения перестановки. | ||
| Строка 164: | Строка 164: | ||
Поскольку перестановка – это частный случай сортировки, то, следовательно, нижняя граница перестановки применима и к сортировке. В маловероятном случае, когда <math>В \; log \; m = o(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>, модель сравнения для доказательства нижней границы сортировки не нужна; сложность сортировки в этом случае возникает не из-за определения порядка данных, а из-за перестановки (или маршрутизации) данных. | ||
Доказательство, использованное выше для перестановок, работает и для перестановочных сетей, в которых схема коммуникаций абстрактна (фиксирована). Поскольку выбор дискового блока фиксирован для каждого t, то здесь нет члена | Доказательство, использованное выше для перестановок, работает и для перестановочных сетей, в которых схема коммуникаций абстрактна (фиксирована). Поскольку выбор дискового блока фиксирован для каждого t, то здесь нет члена N log N, как в (7), и, соответственно, нет аддитивного члена log N во внутреннем выражении, как в (8). Следовательно, решение для t дает нижнюю границу (2), а не (3). Нижняя граница следует непосредственно из рассуждения о подсчете; в отличие от вывода сортировки, она не требует модели сравнения для случая <math>В \; log \; m = o(log \; n)</math>. Эта нижняя граница также непосредственно применима к БПФ, поскольку сети перестановок могут быть образованы из трех последовательных БПФ. Нижняя граница для транспонирования включает потенциальный аргумент, основанный на отношении совместности [2]. | ||