Главная Промышленная автоматика.

ся для считывания или записи данных. Начиная с этого момента дальнейшее увеличение т ведет, по сути, к увеличению полного времени обработки данных, поскольку "узким местом" системы становятся вычисления в основной памяти.

Многофазная сортировка

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

1. В течение одного прохода, когда серии от каждого из т файлов объединяются в серии (т + 1)-го файла, нет нужды использовать все серии от каждого из т входных файлов. Когда какой-либо из файлов становится выходным, он заполняется сериями определенной длины, причем количество этих серий равно минимальному количеству серий, находящихся в сливаемых файлах.

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

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

Пример П.2 Если m = 2, мы начинаем с двух файлов/i и /г, организованных в виде серий длины 1. Записи из Д и /г объединяются, образуя серии длины 2 в третьем файле /з- Выполняется слияние серий до полного опустошения файла /i (здесь для определенности предполагаем, что в файле fi меньше записей, чем в файле /г). Затем объединяем оставшиеся серии длины 1 из /г с таким же количеством серий длины 2 из f. В результате получаются серии длины 3, которые помещаются в файл fy. Затем объединяем серии длины 2 из /з с сериями длины 3 из Эти серии длиной 5 помещаются в файл /2. который был исчерпан во время предыдущего прохода.

Последовательность длин серий 1, 1, 2, 3, 5, 8, 13, 21, ... представляет собой последовательность чисел Фибоначчи. Эта последовательность удовлетворяет рекуррентному соотношению F,- = Fi , + F,.2 для i > 2 с начальными значениями Fq Fi 1. Обратите внимание, что отношение последовательных чисел Фибоначчи Fj.i/F,-приближается к "золотому соотношению" {JE + l)/2= 1.618... по мере увеличения i.

Оказывается, чтобы сохранить нужный ход процесса сортировки (пока не будет отсортирован весь список), начальные количества записей в/, и должны представлять собой два последовательных числа Фибоначчи. Например, в табл. 11.2 показано, что произойдет, если мы начнем наш процесс с и = 34 записями (34 - число Фибоначчи FS), распределенными следующим образом: 13 записей в файле А и 21 запись в файле f2 (13 и 21 представляют собой числа Фибоначчи и F-j, поэтому отношение Рт/Рвравно 1.615, очень близко к 1.618). Состояние файлов в табл. 11.2 показано как а(Ъ), что означает а серий длиной Ь. П

Существуют и другие зависимости меящу длинами серий на разных этапах. Например, длина серий в файле слияния равна сумме длин серий всех файлов предыдущего этапа. - Прим. ред.



Таблица 11.2. Пример лногофазной сортировки После прохода

Вначале

13(1)

21(1)

Пустой

Пустой

8(1)

13(2)

8(3)

Пустой

5(2)

3(3)

5(5)

Пустой

Пустой

2(5)

3(8)

2(13)

Пустой

1(8)

1(13)

1(21)

Пустой

Пустой

Пустой

1(34)

Когда скорость ввода-вывода не является „узким местом"

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

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

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

1. Как мы уже видели, если в нашем распоряжении есть много дисководов или накопителей на магнитной ленте, ввод-вывод можно ускорить настолько, что время для выполнения слияния превысит время ввода-вывода.

2. Может стать экономически выгодным применение более быстродействующих каналов обмена данными.

Поэтому имеет смысл подробнее рассмотреть проблему, с которой можно столкнуться в случае, когда "узким местом" в процессе сортировки слиянием данных, хранящихся во вторичной памяти, становится их объединение. Сделаем следуюшие предположения.

1. Мы объединяем серии, размеры которых намного превышают размеры блоков.

2. Сушествуют два входных и два выходных файла. Входные файлы хранятся на одном внешнем диске (или каком-то другом устройстве, подключенном к основной памяти одним каналом), а выходные файлы - на другом подобном устройстве с одним каналом.

3. Время считывания, записи и выбора для заполнения блока записей с наименьшими ключами среди двух серий, находящихся в данный момент в основной памяти, одинаково.

С учетом этих предположений рассмотрим класс стратегий слияния, которые предусматривают выделение в основной памяти нескольких входных буферов (место для хранения блока). В каждый момент времени какой-то из этих буферов будет содер-•жать невыделенные для слияния записи из двух входных серий, причем одна из них



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

Выполняются (возможно, одновременно) следующие действия.

1. Считывание входного блока во входной буфер.

2. Заполнение одного из выходных буферов выбранными записями, т.е. записями с наименьшими ключами среди тех, которые в настоящий момент находятся во входном буфере.

3. Запись данных другого выходного буфера в один из двух формируемых выходных файлов.

В соответствии с нашими предположениями, эти действия занимают одинаковое время. Для обеспечения максимальной эффективности их следует выполнять параллельно. Это можно делать, если выбор записей с наименьшими ключами не включает записи, считываемые в данный момент. Следовательно, мы должны разработать такую стратегию выбора буферов для считывания, чтобы в начале каждого этапа (состоящего из описанных действий) b невыбранных записей с наименьшими ключами уже находились во входных буферах (Ъ - количество записей, которые заполняют блок или буфер).

Условия, при которых слияние можно выполнять параллельно со считыванием, достаточно просты. Допустим, fei и - наибольшие ключи среди невыбранных записей в основной памяти из первой и второй серий соответственно. В таком случае в основной памяти должно быть по крайней мере Ъ невыбранных записей, ключи которых не превосходят min(/Ji, /гг). Сначала мы покажем, как можно выполнить слияние с шестью буферами (по три на каждый файл), а затем покажем, что будет достаточно четырех буферов, если они будут использоваться совместно для двух файлов.

Схема с шестью входными буферами

Схема работы с шестью входными буферами представлена на рис. 11.2 (два выходных буфера здесь не показаны). Для каждого файла предусмотрены три буфера. Каждый буфер рассчитан на Ъ записей. Заштрихованная область представляет имеющиеся записи, ключи расположены по окружности (по часовой стрелке) в возрастающем порядке. В любой момент времени общее количество невыбранных записей равняется 46 (если только не рассматриваются записи, оставшиеся от объединяемых серий). Поначалу мы считываем в буферы первые два блока из каждой серии. Поскольку у нас всегда имеется 46 записей, а из одного файла может быть не более 36 записей, мы знаем, что имеется по крайней мере Ь записей из каждого файла. Если fci и /гз - наибольшие имеющиеся ключи в двух данных сериях, должно быть 6 записей с ключами, не большими, чем ку, и 6 записей с ключами, не большими, чем ftj. Таким образом, имеются 6 записей с ключами, не большими, чем min(Ai, ftj).

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

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 [102] 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0017