Попытаемся минимизировать эту величину при условии (14), считая для удобства, что Bk не обязаны быть целыми. Если увеличить Bj на J и уменьшить Bk на ту же небольшую величину, то число поисков изменится на

Lj , Lk [ Lj

Bj + 6 Bj Bk -S Bk~ \Bk{Bk - 5) Bj{Bj + 5))

t. e. сумму (15) можно уменьшить, если Lj/Bj ф Lf.lB\. Следовательно, мы получим минимальное число операций поиска только при таком условии:

L\ Lp Lp+i

W = "=W""b-

Поскольку мини.мум обязательно существует, он должен достигаться при

Bk = /TkM/{Дl++/Tl), 1<к<Р+1 (17)

(это единственные значения Bi,..., J5p+i, удовлетворяющие одновременно (14) и (16)). Подставив (17) в (15), можно получить весьма простую формулу для общего числа операций поиска,

(\/Zr+---+\/W)/, (18)

которую можно сравнить с результатом {Р-\- V){Li-\-----\-Lp+i)/M, получающимся в

том случае, если длины всех буферов равны. Как следует из упр. 1.2.3-31, вьшгрыш равен

{.Tj-Vrkf/M. i<j<k<p+i

к сожалению, формула (18) не годится для простого определения оптимальной схемы слияния, как в теореме К (см. упр. 14).

Использование сцепления. В работе М. А. Goetz, САСМ 6 (1963), 245-248, предложен интересный способ связывания отдельных дорожек, благодаря чему исключается поиск при выводе. Для реализации такой идеи требуется почти невообразимый набор программ, управляющих дисками; сама идея применима не только для сортировки, но и для решения многих других задач. Поэтому она может оказаться весьма полезной для выполнения задач общего назначения.

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

Здесь нас подстерегает ловушка. Дело в том, что мы не можем записывать ссылку на следующую дорожку внутри самой дорожки, поскольку необходимая для этого информация в нужный момент неизвестна. (Можно, если это нас устраивает, записать ссылку на предыдущую дорожку и на следующем проходе читать файл в обратном направлении.) Допускается хранение отдельной таблицы адресов связи для дорожек каждого файла, возможно, частично на самом диске. Списки свободного пространства можно компактно представить с помощью битовых таблиц, в которых 1 ООО бит указывает занятость или незанятость 1 ООО дорожек.

Пересмотренный вариант прогнозирования. В алгоритме 5.4.6F показано, как можно предсказать, какой из входных буферов при Р-путевом слиянии освободится первым. Для этого анализируется последний ключ в каждом буфере. В результате можно выполнять чтение и вычисление одновременно. В этом алгоритме используются плавающие входные буфера, не связанные жестко ни с одним из файлов. Таким образом, все буфера могут быть одного размера и можно не использовать каких-либо ухищрений при распределении оперативной памяти для буферов. Ограничения, вытекающие из использования буферов одинакового размера, в настоящее время несущественны, поскольку объем оперативной памяти в современных компьютерах не идет ни в какое сравнение с прежними объемами. Теперь само собой разумеющимся считается выделение буфера объемом в одну дорожку диска.

Таким образом, можно считать, что Р серий, которые нужно слить, состоят из последовательности блоков данных, в которой каждый блок (кроме разве что последнего) содержит ровно В записей. Д. Л. Уитлоу (D. L. Whitlow) и А. Сассон (А. Sasson) разработали интересный алгоритм, названный ими SyncSort [U. S. Patent 4210961 (1980)], который представляет собой усовершенстованный вариант алгоритма 5.4.6F и требует использования всего лишь трех буферов размером В вместе со специальным системным буфером (пулом), в котором можно хранить до РВ записей и РВ указателей. В отличие от этого нового алгоритма, алгоритм 5.4.6F требовал 2Р входных буферов и 2 выходных, но не предполагал буферизации указателей.

Три буфера для SyncSort объединяются в кольцо. В процессе слияния компьютер обрабатывает данные в текущем буфере, в то время как входные данные считываются в следующий буфер, а выходные записьшаются в файл из третьего. Многие модели НМД позволяют записывать и считывать информацию одновременно при обращении к одному и тому же цилиндру. Таким образом, при слиянии можно записывать новые серии на место тех серий, которые считываются. Альтернативный вариант - использовать два диска. Тогда с одного из них выполняется чтение, а на другой производится запись. Если нельзя четко синхронизировать чтение и запись (например, из-за расхождений во времени поиска дорожки), можно включить в кольцо четыре или даже более буферов, как показано на рис. 26 в разделе 1.4.4.

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

Алгоритм слияния SyncSort предполагает обмен каждой записи в текущем буфере со следующей записью на выход, а именно - с записью в системном буфере, имеющей наименьший ключ. Дерево выбора и связи со следующими записями также обновляются по мере необходимости в процессе такого обмена. Как только будет

достигнут конец в текущем буфере, можно "провернуть" кольцо буферов - и буфер считывания станет текущим, буфер записи станет буфером для чтения, а данные из прежнего текущего буфера будут переписываться в выходной файл.

Использование нескольких дисков. Первые накопители на магнитных дисках были устройствами внушительных габаритов и веса, но со временем они стали намного меньше, легче, а главное - дешевле, но емкость их намного возросла. Это совершенно естественно привело к тому, что многие разработчики обратили внимание на создание специальных алгоритмов для ранее немыслимых комплексов из 5, 10 или даже 50 совместно работающих НМД.

Один из способов использования множества дисков - применение технологии разделения данных (disk striping) для больших файлов. Предположим, в нашем распоряжении имеется D НМД, пронумерованных О, 1, ...,£) - 1, и рассмотрим файл, который состоит из L блоков ooOi .. .ai-i- Разделение этого файла на D дисков означает, что блок aj записывается на диск под номером j mod D. Следовательно, на диске О хранятся блоки ооодагс •. •, на диске 1 - 0i0d+i02D+i • • • и т. д. При такой организации можно выполнять D операций чтения или записи одновременно в группах из D блоков aoi.. .ao-i, apao+i - (120-1, которые называются суперблоками. Отдельные блоки в каждом суперблоке должны находиться на соответствующих цилиндрах различных дисков, что обеспечит одинаковое время поиска на каждом устройстве. Теперь мы сможем работать, как если бы в нашем распоряжении был один-единственный диск с этими блоками данных и буфера объемом DB, но операции ввода и вывода выполнялись в D раз быстрее.

Благодаря такой организации разделения данных получается довольно изящный вариант усовершенствования сортировки при выполнении 2-путевого слияния или (в общем случае) всегда, когда необходимо привести в соответствие записи с равными ключами в двух файлах, упорядоченных по ключам. Предположим, что блоки 00О1О2 ... первого файла разделены между D дисками, как описано выше, но блоки 606162 ... другого файла разделены в обратном порядке, т. е. блок bj хранится на диске {D-1-j) mod D. Например, если £) = 5, то блоки Oj находятся соответственно на дисках О, 1, 2, 3, 4, О, 1, ... , а блоки bj, j > О, находятся на дисках 4, 3, 2, 1, О, 4,

з, ... . Пусть aj - последний ключ в блоке Oj, а /3j - последний ключ в блоке bj. Проанализировав блоки а и /3, можно предсказать нужный порядок считывания данных из этих блоков. Например, эта последовательность может иметь вид

О060О1О261 0304620506 0703636465 бббтбвбдбю ....

При D = 5 блоки находятся соответственно на дисках

04123 34201 23104 32104 ...

и, если считывать их по пять одновременно, можно осуществлять ввод безо всяких помех с дисков {0,4,1,2,3}, {3,4,2,0,1}, {2,3,1,0,4}, {3,2,1,0,4}, .... При этом никогда не возникнет конфликт вследствие попытки прочесть одновременно два блока с одного и того же устройства! В общем случае, имея D дисков, можно бесконфликтно считывать D блоков сразу, поскольку при некотором к первая группа будет иметь к блоков оо ... Ofc-i на дисках от О до к-1, а £) -/с блоков Ьо • • bo-k-i - на дисках от D - I до к. Далее можно продолжать в том же духе, но с дисками, номера которых сдвигаются циклически на к.