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

(4) <math>\Theta \bigg( \frac{n}{D} log_m min \{ M, p, q, n \} \bigg),</math>

 

'''где N = pq и n = N/B.'''

(5) <math>\Theta \bigg( \frac{n}{D} \bigg( 1 + \frac{rank( \gamma )}{log \; m} \bigg) \bigg) ,</math>

 

'''где <math>\gamma</math> – подматрица размером log n x log B матрицы A, расположенная в ее левом нижнем углу.'''

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

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

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