4430
правок
Внешние сортировка и перестановка: различия между версиями
Материал из WEGA
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 14:44, 20 мая 2023
, 20 мая 2023→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 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] вывели соответствующую нижнюю границу. | ||
| Строка 181: | Строка 181: | ||
== Применение == | == Применение == | ||
Сортировка и операции, подобные ей, составляют значительную долю компьютерных вычислений [9], | Сортировка и операции, подобные ей, составляют значительную долю компьютерных вычислений [9], а также находят множество применений в базах данных. Кроме того, сортировка является важной парадигмой при разработке эффективных EM-алгоритмов, как показано в [14], где можно найти несколько приложений. С некоторыми техническими оговорками, многие задачи, которые могут быть легко решены за линейное время во внутренней памяти, такие как перестановка, ранжирование списка, оценка дерева выражений и поиск связных компонентов в разреженном графе, требуют такого же количества операций ввода-вывода в PDM, как и сортировка. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Несколько интересных задач остаются нерешенными. Одной из сложных теоретических проблем является доказательство нижних границ для перестановки и сортировки без предположения о неделимости. Другой вопрос заключается в том, как определить стоимость ввода-вывода для каждой отдельной перестановки как функцию некоторой простой характеристики перестановки | Несколько интересных задач остаются нерешенными. Одной из сложных теоретических проблем является доказательство нижних границ для перестановки и сортировки без предположения о неделимости. Другой вопрос заключается в том, как определить стоимость ввода-вывода для каждой отдельной перестановки как функцию от некоторой простой характеристики перестановки – например, от количества инверсий. Постоянной целью является разработка оптимальных EM-алгоритмов и перевод теоретических достижений в заметные улучшения в практическом применении. Любопытные проблемы и возможности в разработке и анализе алгоритмов возникают в связи с появлением новых архитектур, таких как сети рабочих станций, иерархические устройства хранения, дисковые накопители с возможностями обработки, устройства хранения на основе микроэлектромеханических систем (МЭМС). Недавно были представлены активные (или интеллектуальные) диски, в которых дисковые накопители имеют некоторые возможности обработки и могут фильтровать информацию, отправляемую на хост-компьютер, для «расширения» узкого места в виде операций ввода-вывода, особенно в масштабных приложениях баз данных. Энергонезависимая память на основе МЭМС может стать промежуточным уровнем в иерархии памяти между DRAM и дисками. В конечном итоге она может обеспечить лучшие по сравнению с дисками параметры задержки и пропускной способности при меньшей стоимости за бит, чем у DRAM. | ||
== Ссылка на код == | == Ссылка на код == | ||
