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

while not eofifl) or not eof{f2) do begin { слияние двух файлов ) { инициализация } used[l]:= 0; used[2];= 0; fin[l]:= false; fin[2]:= false; getrecordd) ; getrecord{2) :

while not fin[l] or not fin[2] do begin { слияние серий } { вычисление переменной winner (победитель) } if finll] then winner:= 2

{f2 "побеждает" no умолчанию: серия из fl исчерпалась} else if fin[2] then winner:= 1

{fl "побеждает" no умолчанию} else {не исчерпалась ни одна из серий)

if currentll] .key < currentl2] .key then winner-.- 1 else winner:= 2; if outswitch then write(gl, current[ winner] ) else write(g2, current[winner]) ; getrecordiwinner)

end;

{ закончено сли5шие двух серий, далее надо "переключить"

выходной файл и повторить щзоцедуру } outswitch:= not outswitch

end; { merge ]

Обратите внимание, что процедура merge, показанная в листинге 11.1, вовсе не требует, чтобы отдельная серия полностью находилась в памяти: она считывает и записывает последовательно запись за записью. Именно нежелание хранить целые серии в основной памяти заставляет нас использовать два входных файла. В противном случае можно было бы читать по две серии из одного файла одновременно.

Таблица 11.1. Сортировка слиянием

28 31

28 3

3 10

31 5

5 40

93 96

93 10

28 93

10 40

96 40

31 96

54 65 30 90

85 9 39 13

а) исходныефайлы 54 85 30 39

9 65 13 90

б) серии длиной 2

9 54 65 85

13 30 39 90

в) серии длиной 4

8 8

10 8

10 10

8 10

8 22

69 22

10 10 22 69 77

3 5 10 28 31 40 93 96 9 13 30 39 54 65 85 90

г) серии длиной 8 5 9 10 13 28 30 31 39 40 54 8 10 10 22 69 77

д) серии длиной 16 3 5 8 8 9 10 10 10 13 22 28 30 31 39 40 54 65 69 77 85 90 93 96 с) серии длиной 32

65 85 90 93 96



Пример ПЛ. Допустим, есть список из 23 чисел, поделенный на два файла (табл. 11.1,а). Мы начинаем с объединения серий длины 1, создавая два файла, представленных в табл. 11.1,6. Например, первыми сериями длины 1 являются 28 и 31; мы объединяем их, выбрав сначала 28, а затем 31. Следующие две серии единичной длины, 3 и 5, объединяются, образовывая серию длиной 2, и эта серия помещается во второй файл, показанный в табл. 11.1,6. Эти серии разделены в табл. 11.1,6 вертикальными линиями, которые, разумеется, не являются частью файла. Обратите внимание, что второй файл в табл. 11.1,6 имеет хвост единичной длины (запись 22), в то время как у первого файла хвоста нет.

Мы переходим от табл. 11.1,6 к табл. 11.1,в, объединяя серии длины 2. Например, две такие серии (28, 31) и (3, 5) объединяются, образовывая серию (3, 5, 28, 31), показанную в табл. 11.1,в. К моменту, когда мы перейдем к сериям длиной 16 (см. табл. 11.1,д), Один файл будет содержать одну лолную серию, а другой - только хвост длиной 7. На последней стадии, когда файлы должны быть организованы в виде серий длиной 32, у нас будет один файл, содержащий только хвост (длиной 23), и пустой второй файл. Единственная серия длиной 32 будет, конечно же, искомой отсортированной последовательностью чисел. □

Ускорение сортировки слиянием

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

Если, например, у нас есть миллион записей, нам потребуется 20 проходов по этим данным, чтобы выполнить сортировку, начиная с серий длиной 1. Если, однако, у нас есть возможность одновременно поместить в основную память 10 ООО записей, то мы сможем за один проход прочитать 100 групп из 10 ООО записей, отсортировать каждую группу и получить таким образом 100 серий длиной 10 ООО, поделенных поровну между двумя файлами. Таким образом, всего семь проходов и слияний потребовалось бы для сортировки файла, содержащего не более 10 ООО х 2 = 1 280 ООО записей.

Минимизация полного времени выполнения

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

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



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

Чтобы избежать подобных проблем, мы рассматриваем ключи последних записей в последних блоках, считанных из Д и /г, например ключи ftj и fej соответственно. Если какая-либо из серий исчерпалась, мы, естественно, считываем следующую серию из другого файла. Если серия не исчерпалась, мы считываем блок из файла Д, если, конечно, fei < kz (в противном случае считываем блок из /г). То есть, мы определяем, у какой из двух серий будут первой выбраны все ее записи, находящиеся в данный момент в основной памяти, и в первую очередь пополняем запас записей именно для этой серии. Если выбор записей происходит быстрее, чем считывание, мы знаем, что когда будет считан последний блок этих двух серий, для последующего слияния не может остаться больше двух полных блоков записей; возможно, эти записи будут распределены по трем (максимум!) блокам.

Многоканальное слияние

ЕСЛИ "узким местом" является обмен данными между основной и вторичной памятью, возможно, удалось бы сэкономить время за счет увеличения числа каналов обмена данными. Допустим, что в нашей системе имеется 2т дисководов, каждый из которых имеет собственный канал доступа к основной памяти. Мы могли бы разместить на т дисководах т файлов (Д, fz, fm). организованных в виде серий длины к. Тогда можно прочитать т серий, по одной из каждого файла, и объединить их в одну серию длиной mh. Эта серия помещается в один из т выходных файлов (gi.gz, gm), каждый из которых получает по очереди ту или иную серию.

Процесс слияния в основной памяти можно выполнить за O(log т) шагов на одну запись, если мы организуем т записей-кандидатов, т.е. наименьших на данный момент невыбранных записей из каждого файла, в виде частично упорядоченного дерева или другой структуры данных, которая поддерживает операторы INSERT и DELETEMIN, выполняемые над очередями с приоритетами за время порядка O(logra). Чтобы выбрать из очереди с приоритетами запись с наименьшим ключом, надо выполнить оператор DELETEMIN, а затем вставить (оператор INSERT) в очередь с приоритетами следующую запись из файла-победителя в качестве замены выбранной записи.

Если у нас имеется п записей, а длина серий после каждого прохода умножается на т, тогда после i проходов серии будут иметь длину т. Если т > п, т.е. после i = log„ra проходов, весь список будет отсортирован. Так как log„» = log2"/log2n, то "коэффициент экономии" (по количеству считываний каждой записи) составляет log2n. Более того, если т - количество дисководов, используемых для входных файлов, и т дисководов используются для вывода, мы можем обрабатывать данные в т раз быстрее, чем при наличии лишь одного дисковода для ввода и одного дисковода для вывода, я в 2т раз быстрее, чем при наличии лишь одного дисковода для ввода и вывода (входные и выходные файлы хранятся на одном диске). К сожалению, бесконечное увеличение т не приводит к ускорению обработки по "закону коэффициента logm". Причина заключается в том, что при достаточно больших значениях т время, необходимое для слияния в основной памяти (которое растет фактически пропорционально logm), превосходит время, требующее-





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.0036