Половина дорожки данных

Рис. 90. Анализ времени ожидания при чтении половины дорожки.

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

Какой алгоритм сортировки следует использовать? Естественно выбрать метод слияния; другие методы внутренней сортировки не столь хороши в применении к дискам, за исключением, возможно, поразрядных методов, описанных в разделе 5.2.5. Но анализ, приведенный в разделе 5.4.7, показывает, что поразрядная сортировка обычно проигрывает слиянию в большинстве приложений общего назначения, поскольку теорема двойственности, сформулированная в этом разделе, применима к дискам точно так же, как и к лентам. Поразрядная сортировка действительно имеет преимущество в случае, когда ключи равномерно распределены и параллельно используется множество дисков, поскольку исходное распределение цифр ключей может помочь разделить всю процедуру на несколько независимых подпроцессов, никак не обменивающихся инфор.мацией. (См., например, R. С. Agar-wal, SIGMOD Record 25,2 (June, 1996), 240-246.)

В дальнейшем основное внимание будет уделено сортировке методо.м слияния. Чтобы начать такую сортировку, можно использовать выбор с замещением с двумя буферами ввода по 5 000 символов и двумя буферами вывода по 5 000 симвалов. Фактически можно свести требования к оперативной памяти к трем буферам по 5 ООО символов, если замещать записи в текущем буфере ввода записями, выводимыми из дерева выбора. Остается еще 85 000 символов (850 записей) для дерева выбора, так что один проход по данным, которые используются в этой книге в качестве примера, позволит сформировать около 60 начальных серий (см. формулу 5.4.6-(3)). Этот проход занимает лишь около 50 с, если предположить, что скорость внутренней обработки достаточно высока, чтобы успеть за вводом-выводом (каждые 500 мкс в буфер вывода должна передаваться запись). Если же сортируемые исходные данные находятся на НМЛ MIXT, а не на барабане, этот проход будет выполняться медленнее и время будет зависеть от скорости обмена данными с НМЛ.

Нетрудно видеть, что при использовании двух барабанов и при чтении/записи полных дорожек общее время передачи для Р-путевого слияния уменьшается с уве-

личением P. К сожалению, нельзя выполнить одно только 60-путевое слияние всех начальных серий, так как в памяти нет места для 60 буферов. (Если размер буферов будет меньше 5 000 символов, то появится нежелательное время ожидания. Прошу не забьшать, что мы все еще находимся в начале 70-х годов, когда возможности использования оперативной памяти были весьма ограничены.) Если выполнять Р-путевое слияние, переписывая все данные с одного барабана на другой таким образом, что чтение и запись совмещены, то число проходов слияния равно logp 60]; следовательно, можно завершить работу за два прохода, если 8 < Р < 59. С уменьшением Р уменьшается объем сопутствующих вычислений, поэтому выберем Р = 8; если будет образовано 65 начальных серий, выберем Р = 9. Если будет образовано 82 или больше начальных серий, можно взять Р = 10, но, так как имеется место только для 18 буферов ввода и двух буферов вывода, могут возникнуть задержки в процессе слияния (см. алгоритм 5.4.6F). В таком случае, вероятно, лучше выполнить два частичных прохода, обрабатывая небольшую .часть данных, и сократить таким образом число начальных серий до 81 или меньше.

При наших предположениях каждый проход слияния займет около 50 с, так что вся сортировка в этой идеальной ситуации будет завершена за 2.5 мин (плюс несколько секунд на инициализацию и другие вспомогательные операции). Это в шесть раз быстрее, чем при наилучшей из сортировок с шестью лентами, рассмотренных в разделе 5.4.6. Причинами такого ускорения являются увеличенная скорость передачи данных между внешней и оперативной памятью (она в 3.5 раза выше), более высокий порядок слияния (мы не можем осуществить 8-путевое слияние на лентах, не имея девяти или более лент) и то, что выводные данные остаются на диске (нет необходимости в заключительной перемотке и других аналогичных операциях). Если исходные данные и рассортированный результат должны находиться на НМЛ MIXT, а барабаны использоваться только для слияния, то понадобится около 8.2 мин.

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

В разделе 5.4.4 рассказывалось, что схемы слияния можно изображать с помощью деревьев и что время передачи, соответствующее схеме слияния, пропорционально длине внешнего пути дерева. В качестве схем эффективного слияния на лентах можно использовать лишь определенные виды деревьев (T-Iifo или сильные T-fifo), потому что в процессе слияния некоторые серии оказываются "спрятанными" в середине ленты. Но при использовании дисков или барабанов пригодны любые деревья, если только степени их внутренних узлов не слишком велики (т. е. согласуются с действительным объемом внутренней памяти).

Следовательно, время передачи можно минимизировать, если выбрать дерево с минимальной длиной внепшего пути, такое, как полное Р-арное дерево, где Р - наибольшее возможное значение. По формуле 5.4.4-(9) длина внешнего пути такого дерева с 5 внешними узлами (листьями) равна

logp 5

95-[(P-5)/(P-l)J,

Особенно просто строится алгоритм, который осуществляет слияние в соответствии со схемой полного Р-арного дерева. (См., например, рис. 91, на котором показан случай, когда Р = 3, 5 = 6.) Сначала добавляем, если необходимо, фиктивные серии, чтобы сделать 5 = 1 (по модулю Р - 1), затем объединяем серии в соответствии с правилом "первым включается - первым исключается" сливая на каждом этапе Р самых "старых" серий в начале очереди в одну серию, помещаемую в конец.

Рис. 91. Полное тернарное дерево с шестью листьями и соответствующая схема слияния.

Полные Р-арные деревья дают оптимальную схему, если все серии имеют равную длину, но часто результат может быть еще лучше, если одни серии длиннее других. Можно без труда построить оптимальную схему для этой общей ситуации с помощью метода Хаффмэна (упр. 2.3.4.5-10), который применительно к слиянию формулируется так: "сначала добавьте (1 - 5) mod (Р - 1) фиктивных серий длиной О, затем многократно выполните слияние Р кратчайших из имеющихся серий, пока не останется одна серия" Если все начальные серии имеют одинаковую длину, этот метод сводится к описанной выше дисциплине FIFO.

В нашем примере с обработкой 100,000 записей можно выполнять 9-путевое слияние, так как в памяти поместятся 18 буферов ввода и два буфера вывода и в алгоритме 5.4.6F будет достигнуто полное совмещение вычислений. Полное 9-арное дерево с 60 листьями соответствует схеме слияния с l прохода, если все начальные серии имеют одинаковую длину. Общее время сортировки с одним барабаном и с использованием контрольного чтения после каждой записи становится, таким образом, равным 7.4 мин. Увеличивая Р, можно немного уменьшить это время, но ситуация будет весьма запутанной, поскольку не исключается задержка чтения в связи с тем, что буфера могут оказаться слишком полными или слишком пустыми.

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