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

Одним из требований является выбор S - 1 элементов разбиения таким образом, чтобы корзины были примерно одинакового размера. В этом случае размеры корзин уменьшаются от одного уровня рекурсии к другому на относительный коэффициент <math>\Theta(S)</math>, и, таким образом, существует <math>O(log_S \; n)</math> уровней рекурсии. На каждом уровне рекурсии выполняется сканирование данных. По мере прохождения элементов через внутреннюю память они разбиваются на S корзин в онлайновом режиме. Когда буфер размером B заполняется для одной из корзин, его блок записывается на диски при следующем вводе-выводе, и для хранения следующего набора входящих элементов для этой корзины используется другой буфер. Таким образом, максимальное число корзин (и элементов разбиения) равно <math>S = \Theta(M/B) = \Theta(m)</math>, а результирующее число уровней рекурсии равно <math>\Theta(log_m \; n)</math>. Как выполнить каждый уровень рекурсии за линейное число операций ввода-вывода, обсуждается в [2,11,16].

Еще более эффективным способом сортировки распределением, и при этом детерминированным, является метод BalanceSort, разработанный Нодином и Виттером [11]. В ходе процесса разделения алгоритм отслеживает, насколько равномерно на данный момент каждая корзина была распределена между дисками. Он поддерживает инвариант, который гарантирует хорошее распределение по дискам для каждой корзины.

Упомянутые выше методы сортировки распределением для параллельных дисков выполняют операции записи на целых полосах, что облегчает запись информации о четности для последующего использования при коррекции и восстановлении ошибок. Но поскольку блоки, записанные на каждой полосе, обычно принадлежат нескольким корзинам, сами корзины не будут чередоваться на дисках, и поэтому диски должны использоваться независимо во время операций чтения. Поэтому на этапе записи каждая корзина должна отслеживать последний блок, записанный на каждый диск, чтобы блоки для этой корзины можно было связать вместе.

В этом новом сценарии основной цикл алгоритма сортировки распределением, как и раньше, заключается в чтении одного блока памяти за раз и разбиении элементов на S корзин. Однако, в отличие от предыдущего варианта, блоки для каждого отдельной корзины будут располагаться на дисках в смежных полосах. Поэтому у каждого блока есть заранее определенное место, куда он должен быть записан. При обычном циклическом упорядочивании полос (например, ... , 1, 2, 3, ... , D, 1, 2, 3, ... , D, ... ) блоки из разных корзин могут «столкнуться» в том смысле, что их нужно будет записать на один и тот же диск, и последующие блоки в тех же корзинах также будут сталкиваться. Виттеру и Хатчинсону [15] удалось разрешить эту проблему с помощью техники ''рандомизированного зацикливания''. Для каждой из S корзин они определяют порядок дисков в полосе для этой корзины с помощью случайной перестановки {1, 2, .... , D}. S случайных перестановок выбираются независимым образом. Если два блока (из разных корзин) случайно сталкиваются во время записи на один и тот же диск, то один блок записывается на диск, а другой остается в очереди на запись. С высокой вероятностью последующие блоки из этих двух корзин будут записаны на разные диски и, таким образом, не столкнутся. Для случая, когда существует небольшой запас доступного буферного пространства для временного кэширования блоков в очередях на запись, Виттер и Хатчинсон [15] показывают, что с высокой вероятностью запись происходит оптимально.

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

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

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

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

Сортировка и операции, подобные ей, составляют значительную долю компьютерных вычислений [9], при этом они находят множество применений в базах данных. Кроме того, сортировка является важной парадигмой при разработке эффективных EM-алгоритмов, как показано в [14], где можно найти несколько приложений. С некоторыми техническими оговорками, многие проблемы, которые могут быть легко решены за линейное время во внутренней памяти, такие как перестановка, ранжирование списка, оценка дерева выражений и поиск связных компонентов в разреженном графе, требуют такого же количества операций ввода-вывода в PDM, как и сортировка.

Несколько интересных задач остаются нерешенными. Одной из сложных теоретических проблем является доказательство нижних границ для перестановки и сортировки без предположения о неделимости. Другой вопрос заключается в том, как определить стоимость ввода-вывода для каждой отдельной перестановки как функцию некоторой простой характеристики перестановки, например, количества инверсий. Постоянной целью является разработка оптимальных EM-алгоритмов и перевод теоретических достижений в заметные улучшения в практическом применении. Любопытные проблемы и возможности в разработке и анализе алгоритмов возникают в связи с появлением новых архитектур, таких как сети рабочих станций, иерархические устройства хранения, дисковые накопители с возможностями обработки и устройства хранения на основе микроэлектромеханических систем (МЭМС). Недавно были предложены активные (или интеллектуальные) диски, в которых дисковые накопители имеют некоторые возможности обработки и могут фильтровать информацию, отправляемую на хост-компьютер, для «расширения» узкого места в виде операций ввода-вывода, особенно в масштабных приложениях баз данных. Энергонезависимая память на основе МЭМС может стать промежуточным уровнем в иерархии памяти между DRAM и дисками. В конечном итоге она может обеспечить лучшие по сравнению с дисками параметры задержки и пропускной способности при меньшей стоимости за бит, чем у DRAM.