10. [М23] Используя анализ, проведенный в разделах 5.4.2 и 5.4.3, покажите, что длина каждой перемотки во время стандартного многофазного слияния с шестью лентами или каскадного слияния редко превышает 54% длины файла (исключая начальную и конечную перемотки, которые охватывают весь файл).

11. [23] Откорректировав соответствующие элементы табл. 1, оцените, сколько времени заняло бы выполнение первых девяти примеров на диаграмме А, если бы мы имели двух-скоростную перемотку (быструю и медленную). Считайте, что р - 1, если лента заполнена меньше чем на одну четверть, а для более заполненной ленты время перемотки равно приблизительно 5 с плюс то время, которое получилось бы при р = . Измените пример 8 так, чтобы в нем использовалось каскадное слияние с копированием, поскольку перемотка и прямое чтение в этом случае происходят медленнее копирования. [Указание. Используйте результат упр. 10.]

12. [40] Рассмотрим разбиение шести лент на три пары лент, где каждая пара играет роль одной ленты в многофазном слиянии с Т = 3. Одна лента каждой пары будет содержать блоки 1, 3, 5,..., а другая - блоки 2,4,6,...; таким способом мы, по существу, добиваемся того, чтобы во все время слияния две вводные и две выводные ленты оставались активными, причем эффективная скорость слияния удваивается.

a) Найдите подходящий способ распространения алгоритма F на этот случай.

b) Оцените общее время выполнения, которое получилось бы, если бы этот метод использовался для сортировки 100,000 записей по 100 символов, рассмотрев случаи как прямого, так и обратного чтения.

13. [20] Может ли метод осциллирующей сортировки с пятью лентами в том виде, в котором он определен в алгоритме 5.4.5В, использоваться для сортировки четырех полных бобин исходных данных до момента окончательного слияния?

14. [М19] Выведите (10).

15. [НМ29] Докажите, что зр(г) = /1р(г)/(1 - г), где /гр(г) является рациональной функцией г, не имеющей особых точек внутри единичного круга; следовательно, ai*" = кд(1)п+ 0(1) при п -> оо. В частности, покажите, что

кз(1) = det

/О -ро О О \

О 1-pi -ро О

О -р2 1-pi -ро

МО О О /

/1 -Ро О О

1 1-pi -ро О

1 -Р2 1-pi -Ро

Vo О -1 1 /

16. [41] Детально изучите сортировку 100,000 записей по 100 символов, нарисуйте диаграммы, подобные диаграмме А, в предположении, что имеется 3, 4 и 5 лент.

*5.4.7. Внешняя поразрядная сортировка

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

Предположим, например, что в нашем распоряжении имеются четыре ленты, а ключей может быть только восемь: О, 1, 2, 3, 4, 5, б, 7. Если исходные данные

содержатся на ленте Т1, то начнем с переписи всех четных ключей на ТЗ и всех нечетных - на Т4.

Т1 Т2 ТЗ Т4

Дано {0,1,2,3,4,5,6,7}

Проход 1 - - {0,2,4,6} {1,3,5,7}

Теперь перематываем ленты и читаем сначала ТЗ, а затем - Т4, переписывая {О, 1, 4, 5} на Т1 и {2, 3, 6, 7} на Т2.

Проход 2 {0,4}{1,5} {2,6}{3,7} - -

(Строка "{0,4}{1,5}" обозначает файл, содержащий записи только с ключами О и 4, за которыми следуют записи только с ключами 1 и 5. Заметим, что на Т1 теперь находятся те ключи, средний двоичный разряд которых содержит 0.) После еще одной перемотки и распределения ключей О, 1, 2, 3 на ТЗ и ключей 4, 5, 6, 7 на Т4 получаем следующее.

Проход 3 {0}{1}{2}{3} {4}{5}{6}{7}

После копирования Т4 в конец ТЗ работа завершается. В общем случае для ключей в диапазоне от О до 2* - 1 можно аналогичным образом рассортировать файл за к проходов, после которых следует фаза окончательной "сборки". На этом этапе примерно половина данных копируется с одной ленты на другую. Имея шесть лент, можно так же использовать представления по основанию 3 для сортировки ключей от О до 3* - 1 за А; проходов.

Существуют модификации этого метода с частичными проходами. Предположим, например, что допускается десять ключей {0,1,...,9}, и рассмотрим следу-юц;ую процедуру, авторство которой принадлежит Р. Л. Эшенхерсту (R. L. Ashen-hurst) [Theory of Switching, Progress Report BL-7 (Harvard Univ. Сотр. Laboratory: May, 1954), 1.1-1.76].

Фаза Tl T2 T3 T4 Проход

{0,1,...,9}

1 - {0,2,4,7} {1,5,6} {3,8,9} 1.0

2 {0} - {1,5,6}{2,7} {3,8,9}{4} 0.4

3 {0}{1}{2} {б}{7} - {3,8,9}{4}{o} 0.5

4 {0}{1}{2}{3} {6}{7}{8} {9} {4}{5} 0.3 С {0}{1}{2}{3}{4}...{9} 0

Здесь С представляет фазу сборки. Если каждое значение ключа встречается примерно в одном из десяти случаев, то эта процедура для сортировки десяти ключей затрачивает только 2.8 прохода, в то время как в первом примере требуется 3.5 прохода для сортировки всего восьми ключей. Таким образом, продуманая схема распределения влечет за собой значительное различие в показателях эффективности для поразрядной сортировки точно так же, как для слияния.

Схемы распределения из предыдущих примеров представим, как и обычно, древовидными структурами.

Круглые внутренние узлы этих деревьев пронумерованы 1, 2, 3, ... в соответствии с шагами процесса 1, 2, 3, .... Имена лент А, В, С, D (вместо Т1, Т2, ТЗ, Т4) помещены рядом с ребрами дерева, чтобы указать, куда попадают записи. Квадратные внешние узлы изображают фрагменты файла, содержащие только один ключ, и этот ключ выделен полужирным шрифтом под соответствующим узлом. Ребра, расположенные над квадратными узлами, помечены именем выводной ленты (С в первом примере, А - во втором).

Таким образом, на шаге 3 примера 1 выполняется считывание с ленты D и запись ключей 1 и 5 на ленту А и ключей 3 и 7 на ленту В. Нетрудно видеть, что число выполняемых проходов равно длине внешнего пути дерева, деленной на число внешних узлов в предположении, что все ключи равновероятны.

В связи с последовательной природой ленты и в соответствии с правилом "первым включается - первым исключается" которому подчиняется прямое чтение, нельзя взять за основу схемы распределения любое помеченное дерево. В дереве примера 1 данные записываются на ленту А на шагах 2 и 3; данные, записанные в течение шага 2, необходимо использовать раньше данных, записанных в течение шага 3. В общем случае, если осуществляется запись на ленту в течение шагов г и j, где г < j, первыми следует использовать данные, записанные в течение шага г. Если дерево содержит две ветви вида

г < j,

то должно выполняться условие к < I. Кроме того, нельзя ничего записывать на ленту А между шагами к и I, поскольку между чтением и записью необходима перемотка.

Те читатели, которые внимательно проработали упражнения из раздела 5.4.4, сразу поймут, что допустимые деревья для поразрядной сортировки с прямым чтением на Т лентах - это в точности сильные T-fifo-деревья, описывающие сортировку методом слияния на Т лентах с прямым чтением! (См. упр. 5.4.4-20.) Единственное различие заключается в том, что все внешние узлы рассматриваемых здесь