Структуры данных и алгоритмы (1021739), страница 83
Текст из файла (страница 83)
Устанавливается fin[i]=true, если достигнутконец серии или файла }beginused[i]:= used[i] + 1;if (used[i}= k) or(i = 1) and eof(fl) or( 1 = 2 ) and eof(f2) then fin[i]:= trueelse if i = 1 then read(fl, current[1])else read(f2, current[2])end; { getrecord }begin { merge }outswitch:= true; {первая объединенная серия записывается в gl}rewrite(gl); rewrite(g2);reset(fl); reset(f2);314ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИwhile not eof(fl) or not eof(f2) do begin { слияние двух файлов }{ инициализация }used[l]:= 0; used[2]:= 0;fin[l]:= false; fin[2]:= false;getrecord(1) ; getrecord(2) ;'while not fin[l] or not fin[2] do begin { слияние серий }{ вычисление переменной winner (победитель) }if fin[l] then winner:= 2[f2 "побеждает" по умолчанию: серия из fl исчерпалась).
, else if fin[2] then winner:= 1{.fl "побеждает" по умолчанию)else {не исчерпалась ни одна из серий)if currant[1].key < current[2].key then winner:= 1else winner:= 2;if outswitch then write(gl, current[winner])else write(g2, current[winner]);getrecord(winner)end;{ закончено слияние двух серий, далее надо "переключить"выходной файл и повторить процедуру }outswitch:= not outswitchendend; { merge }Обратите внимание, что процедура merge, показанная в листинге 11.1, вовсе нетребует, чтобы отдельная серия полностью находилась в памяти: она считывает и записывает последовательно запись за записью. Именно нежелание хранить целые серии в основной памяти заставляет нас использовать два входных файла. В противномслучае можно было бы читать по две серии из одного файла одновременно.Габлица11.1. Сортировка слиянием289310543196408565309010698^ 939138771022а) исходные файлы28319396543510409853039810865139069772210б) серии длиной 235283195465851040939613303990881069102277в) серии длиной 43510 2828 319 13 30 39395440 93 968 81010 22697765 85 90г) серии длиной 838101013283010226977313940546585909396д) серии длиной 163 5 8 8 9 10 10 10 13 22 28 30 31 39 40 54 65 69 77 85 90 93 96с) серии длиной 3211.2.
ВНЕШНЯЯ СОРТИРОВКА315Пример 11.1. Допустим, есть список из 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. Мы сэкономили бы немало времени, если бы начали этупроцедуру с прохода, который считывает в основную память группы из k записей(при соответствующем k), сортирует их (например, с помощью процедуры быстройсортировки) и записывает во внешнюю память в виде серии длиной k.Если, например, у нас есть миллион записей, нам потребуется 20 проходов поэтим данным, чтобы выполнить сортировку, начиная с серий длиной 1. Если, однако, у нас есть возможность одновременно поместить в основную память 10 000 записей, то мы сможем за один проход прочитать 100 групп из 10 000 записей, отсортировать каждую группу и получить таким образом 100 серий длиной 10 000, поделенных поровну между двумя файлами.
Таким образом, всего семь проходов и слиянийпотребовалось бы для сортировки файла, содержащего не более 10 000 х 27 =1 280 000 записей.Минимизация полного времени выполненияВ современных компьютерных системах с разделением времени пользователюобычно не приходится платить за время, в течение которого его программа ожидаетсчитывания блоков данных из файла (операция, характерная для процесса сортировки слиянием). Между тем, полное время выполнения сортировки превышает(зачастую значительно) время обработки данных, находящихся в основной памяти.Если же нам приходится сортировать действительно большие файлы, время обработки которых измеряется часами, полное время становится критической величиной,даже если мы не платим за него из собственного кармана, и проблема минимизацииполного времени процесса сортировки слиянием выходит на первый план.Как уже указывалось, время, необходимое для считывания данных с магнитногодиска или магнитной ленты, как правило, существенно превышает время, затрачиваемое на выполнение простых вычислений с этими данными (например, слияниясписков).
Таким образом, можно предположить, что при наличии лишь одного канала, по которому происходит обмен данными с основной памятью, именно этот канали станет тем "узким местом", которое будет тормозить работу системы в целом. Этотканал обмена данными все время будет занят, и полное время работы системы будетпрактически равно времени, затрачиваемому на обмен данными с основной памятью,т.е.
все вычисления будут выполняться практически мгновенно после того, как появятся соответствующие данные, и одновременно с тем, пока будет считываться илизаписываться следующая порция данных.316ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИДаже в условиях такой относительно простой вычислительной среды следует позаботиться о минимизации затрат времени. Чтобы увидеть, что может произойти, если пренебречь этим требованием о минимизации временных затрат, допустим, чтомы выполняем попеременное поблочное считывание двух входных файлов f i и /2.Файлы организованы в виде серий определенной длины, намного превышающей размер блока, поэтому, чтобы объединить две такие серии, нам нужно прочитать несколько блоков из каждого файла. Предположим, однако, что все записи в серии изфайла Д предшествуют всем записям из файла /2.
В этом случае при попеременномсчитывании блоков все блоки из файла /2 должны оставаться в основной памяти. Основной памяти может не хватить для всех этих блоков, но даже если и хватит, нампридется (после считывания всех блоков серии) подождать, пока не будет скопирована и записана вся серия из файла /2.Чтобы избежать подобных проблем, мы рассматриваем ключи последних записейв последних блоках, считанных из Д и /2. например ключи ftj и kz соответственно.Если какая-либо из серий исчерпалась, мы, естественно, считываем следующую серию из другого файла. Если серия не исчерпалась, мы считываем блок из файла Д,если, конечно, fei < k2 (в противном случае считываем блок из /2).
То есть, мы определяем, у какой из двух серий будут первой выбраны все ее записи, находящиеся вданный момент в основной памяти, и в первую очередь пополняем запас записейименно для этой серии. Если выбор записей происходит быстрее, чем считывание,мы знаем, что когда будет считан последний блок этих двух серий, для последующего слияния не может остаться больше двух полных блоков записей; возможно, этизаписи будут распределены по трем (максимум!) блокам.Многоканальное слияниеЕСЛИ "узким местом" является обмен данными между основной и вторичной памятью, возможно, удалось бы сэкономить время за счет увеличения числа каналовобмена данными. Допустим, что в нашей системе имеется 2т дисководов, каждый изкоторых имеет собственный канал доступа к основной памяти. Мы могли бы разместить на т дисководах т файлов (Д, f2, .... fm), организованных в виде серий длины k.Тогда можно прочитать т серий, по одной из каждого файла, и объединить их в однусерию длиной mk.
Эта серия помещается в один из т выходных файлов (gi, g2, ..., gm),каждый из которых получает по очереди ту или иную серию.Процесс слияния в основной памяти можно выполнить за O(log т) шагов на однузапись, если мы организуем т записей-кандидатов, т.е.
наименьших на данный момент невыбранных записей из каждого файла, в виде частично упорядоченного дерева или другой структуры данных, которая поддерживает операторы INSERT иDELETEMIN, выполняемые над очередями с приоритетами за время порядка O(logw).Чтобы выбрать из очереди с приоритетами запись с наименьшим ключом, надовыполнить оператор DELETEMIN, а затем вставить (оператор INSERT) в очередьс приоритетами следующую запись из файла-победителя в качестве замены выбранной записи.Если у нас имеется п записей, а длина серий после каждого прохода умножается на т, тогда после i проходов серии будут иметь длину т1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
