Структуры данных и алгоритмы (1021739), страница 84
Текст из файла (страница 84)
Если т' > п,т.е. после i = log m n проходов, весь список будет отсортирован. Так какlogm« = Iog 2 n/log 2 /n, то "коэффициент экономии" (по количеству считываний каждой записи) составляет Iog2m. Более того, если т — количество дисководов, используемых для входных файлов, и т дисководов используются для вывода, мы можемобрабатывать данные в т раз быстрее, чем при наличии лишь одного дисковода дляввода и одного дисковода для вывода, и в 2т раз быстрее, чем при наличии лишьодного дисковода для ввода и вывода (входные и выходные файлы хранятся на одном диске).
К сожалению, бесконечное увеличение т не приводит к ускорению обработки по "закону коэффициента logm". Причина заключается в том, что при достаточно больших значениях т время, необходимое для слияния в основной памяти(которое растет фактически пропорционально log/n), превосходит время, требующее11.2. ВНЕШНЯЯ СОРТИРОВКА317ся для считывания или записи данных.
Начиная с этого момента дальнейшее увеличение т ведет, по сути, к увеличению полного времени обработки данных, поскольку"узким местом" системы становятся вычисления в основной памяти.Многофазная сортировкаМногоканальную (m-канальную) сортировку слиянием можно выполнить с помощью лишь т + 1 файлов (в отличие от описанной выше 2от-файловой стратегии).При этом выполняется ряд проходов с объединением серий из т файлов в болеедлинные серии в (т + 1)-м файле. Вот последовательные шаги такой процедуры.1.В течение одного прохода, когда серии от каждого из т файлов объединяются всерии (т + 1)-го файла, нет нужды использовать все серии от каждого из твходных файлов. Когда какой-либо из файлов становится выходным, он заполняется сериями определенной длины, причем количество этих серий равно минимальному количеству серий, находящихся в сливаемых файлах.2.
В результате каждого прохода получаются файлы разной длины. Поскольку каждый из файлов, загруженных сериями в результате предшествующих т проходов, вносит свой вклад в серии текущего прохода, длина всех серий на определенном проходе представляет собой сумму длин серий, созданных за предшествующие т проходов. (Если выполнено менее m проходов, можно считать, чтогипотетические проходы, выполненные до первого прохода, создавали сериидлины I.)1Подобный процесс сортировки слиянием называется многофазной сортировкой.Точный подсчет требуемого количества проходов как функции от т (количествафайлов) и п (количество записей), а также нахождения оптимального начальногораспределения серий между т файлами оставлен для упражнений.
Однако мы приведем здесь один пример общего характера.Пример 11.2. Если т = 2, мы начинаем с двух файлов f\ и f%, организованных ввиде серий длины 1. Записи из f\ и /2 объединяются, образуя серии длины 2 в третьем файле /з- Выполняется слияние серий до полного опустошения файла fi (здесь дляопределенности предполагаем, что в файле fi меньше записей, чем в файле fz). Затемобъединяем оставшиеся серии длины 1 из /2 с таким же количеством серий длины 2из /3. В результате получаются серии длины 3, которые помещаются в файл Д.
Затемобъединяем серии длины 2 из f 3 с сериями длины 3 из Д. Эти серии длиной 5 помещаются в файл /2. который был исчерпан во время предыдущего прохода.Последовательность длин серий 1, 1, 2, 3, 5, 8, 13, 21, ... представляет собойпоследовательность чисел Фибоначчи. Эта последовательность удовлетворяет рекуррентному соотношению Ft = Ft_i + F^ для i > 2 с начальными значениямиF0 = FI = 1. Обратите внимание, что отношение последовательных чисел Фибоначчи FI.I/FI приближается к "золотому соотношению" (>/5+1)/2 = 1.618... по мереувеличения i.Оказывается, чтобы сохранить нужный ход процесса сортировки (пока не будетотсортирован весь список), начальные количества записей в fi и f2 должны представлять собой два последовательных числа Фибоначчи.
Например, в табл. 11.2 показано, что произойдет, если мы начнем наш процесс с п = 34 записями (34 — число Фибоначчи FS), распределенными следующим образом: 13 записей в файле f i и 21 запись в файле /2 (13 и 21 представляют собой числа Фибоначчи F6 и FT, поэтомуотношение F7/F6 равно 1.615, очень близко к 1.618). Состояние файлов в табл. 11.2показано как а(Ъ), что означает а серий длиной Ь.
П1Существуют и другие зависимости между длинами серий на разных этапах. Например,длина серий в файле слияния равна сумме длин серий всех файлов предыдущего этапа. —Прим. ред.318ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИ:. . ... •..:..'••.т ,.•'>..•.,.:'.:•:•:Таблица 11.2.
Пример ЛАНОГ офазнои сортировкиПосле прохода/1Вначале123456713(1)Пустой8(3)3(3)Пустой2(13)1(13)Пустой..•::-••-,:••-/2h21(1)Пустой13(2)5(2)Пустой3(8)1(8)Пустой1(34)8(1)Пустой5(5)2(5)Пустой1(21)ПустойКогда скорость ввода-вывода не является „узким местом"Когда "узким местом" является считывание файлов, необходимо очень тщательновыбирать блок, который должен считываться следующим. Как мы уже указывали,нужно избегать ситуаций, когда требуется запоминать много блоков одной серии, поскольку в этой серии наверняка имеются записи с большими значениями ключей,которые будут выбраны только после большинства (или всех) записей другой серии.Чтобы избежать этой ситуации, нужно быстро определить, какая серия первой исчерпает те свои записи, которые в данный момент находятся в основной памяти (этуоценку можно сделать, сравнив последние считанные записи из каждого файла).Если время, необходимое для считывания данных в основную память, сопоставимо со временем, которое занимает обработка этих данных (или даже меньше его),тщательный выбор входного файла, из которого будет считываться блок, становитсяеще более важной задачей, поскольку иначе трудно сформировать резерв записей восновной памяти.Рассмотрим случай, когда "узким местом" является слияние, а не считываниеили запись данных.
Это может произойти по следующим причинам.1.Как мы уже видели, если в нашем распоряжении есть много дисководов или накопителей на магнитной ленте, ввод-вывод можно ускорить настолько, что времядля выполнения слияния превысит время ввода-вывода.2. Может стать экономически выгодным применение более быстродействующих каналов обмена данными.Поэтому имеет смысл подробнее рассмотреть проблему, с которой можно столкнуться в случае, когда "узким местом" в процессе сортировки слиянием данных,хранящихся во вторичной памяти, становится их объединение. Сделаем следующиепредположения.1.2.Мы объединяем серии, размеры которых намного превышают размеры блоков.Существуют два входных и два выходных файла.
Входные файлы хранятся наодном внешнем диске (или каком-то другом устройстве, подключенном к основной памяти одним каналом), а выходные файлы — на другом подобном устройстве с одним каналом.3. Время считывания, записи и выбора для заполнения блока записей с наименьшими ключами среди двух серий, находящихся в данный момент в основнойпамяти, одинаково.С учетом этих предположений рассмотрим класс стратегий слияния, которые предусматривают выделение в основной памяти нескольких входных буферов (место дляхранения блока).
В каждый момент времени какой-то из этих буферов будет содержать невыделенные для слияния записи из двух входных серий, причем одна из них11.2. ВНЕШНЯЯ СОРТИРОВКА.319будет находиться в состоянии считывания из входного файла. Два других буфера будут содержать выходные записи, т.е. выделенные записи в надлежащим образомобъединенной последовательности. В каждый момент времени один из этих буферовнаходится в состоянии записи в один из выходных файлов, а другой заполняется записями, выбранными из входных буферов.Выполняются (возможно, одновременно) следующие действия.1.2.Считывание входного блока во входной буфер.Заполнение одного из выходных буферов выбранными записями, т.е.
записями снаименьшими ключами среди тех, которые в настоящий момент находятся вовходном буфере.3. Запись данных другого выходного буфера в один из двух формируемых выходных файлов.В соответствии с нашими предположениями, эти действия занимают одинаковоевремя. Для обеспечения максимальной эффективности их следует выполнять параллельно. Это можно делать, если выбор записей с наименьшими ключами не включаетзаписи, считываемые в данный момент.1 Следовательно, мы должны разработать такую стратегию выбора буферов для считывания, чтобы в начале каждого этапа(состоящего из описанных действий) b невыбранных записей с наименьшими ключами уже находились во входных буферах (Ъ — количество записей, которые заполняют блок или буфер).Условия, при которых слияние можно выполнять параллельно со считыванием,достаточно просты.
Допустим, kl и k% — наибольшие ключи среди невыбранных записей в основной памяти из первой и второй серий соответственно. В таком случае восновной памяти должно быть по крайней мере Ъ невыбранных записей, ключи которых не превосходят min(fej, k2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
