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

бы хранить адрес бдока, а ддина бдока составдяет 4096 байт, тогда корневой бдок может содержать указатели максимум на 1024 бдока. Таким образом, файды, состоящие максимум из 1024 блоков (т.е. примерно четырех миллионов байт), можно представить одним корневым блоком и блоками, содержащими сам файл. Файды, состоящие из максимум 2" блоков, иди 2 байт, можно представить одним корневым блоком, указывающим на 1024 бдока промежуточного уровня, каждый из которых указывает на 1024 блока-листа, содержащих определенную часть файла, и т.д.

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

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

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

Стоимость операций со вторичной памятью

Природа устройств вторичной памяти (например, дисководов) такова, что время, необходимое ддя поиска бдока и чтения его в основную память, достаточно велико в сравнении со временем, которое требуется ддя относительно простой обработки данных, содержащихся в этом блоке. Допустим, например, что у нас имеется бдок из 1000 целых чисел на диске, вращающемся со скоростью 1000 об/мин. Время, которое требуется ддя позиционирования считывающей головки над дорожкой, содержащей этот бдок (так называемое время установки головок), плюс время, затрачиваемое на ожидание, пока требуемый бдок сделает оборот и окажется под головкой (время ожидания ), может в среднем составлять 100 миллисекунд. Процесс записи бдока в определенное место во вторичной памяти занимает примерно столько же времени. Однако за те же 100 миллисекунд машина, как правило, успевает выполнить 100 ООО команд. Этого времени более чем достаточно, чтобы выполнить простую обработку тысячи целых чисел, когда они находятся в основной памяти (например, их суммирование иди нахождение среди них наибольшего числа). Этого времени может даже хватить ддя выполнения быстрой сортировки целых чисел.

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



11.2. Внешняя сортировка

Сортировка данных, организованных в виде файлов, или - в более общем случае - сортировка данных, хранящихся во вторичной памяти, называется внешней сортировкой. Приступая к изучению внешней сортировки, сделаем предположение, что данные хранятся в Pascal-файле. Мы покажем, как алгоритм сортировки слиянием позволяет отсортировать файл с п записями всего лишь за O(logra) проходов через файл; этот показатель намного лучше, чем 0(п) проходов, которые требовались алгоритмам, изучавшимся в главе 8. Затем мы рассмотрим, как использовать определенные возможности операционной системы по управлению чтением и записью блоков, что может ускорить сортировку за счет сокращения времени "бездействия" компьютера (периоды ожидания, пока блок будет прочитан в основную память или записан из основной памяти вр внешнюю).

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

Главная идея, которая лежит в основе сортировки слиянием, заключается в том, что мы организуем файл в виде постепенно увеличивающихся серий, т.е. последовательностей записей г,, ... ,г, где ключ г, не больше, чем ключ 1 < / < к} Мы говорим, что файл, состоящий из ri.....г„ записей, делится на серии длиной к, если

для всех / > О, таких, что ki < т и rj,(, ,)+i, 7-j,(, i,+2, ... , Ги является последовательностью длиной к. Если т не делится нацело на k, т.е. т = рк + q, тле q < к, тогда последовательность записей r„-g+i, г„ 4.2. - > г„, называемая хвостом, представляет собой серию длиной q. Например, последовательность целых чисел, показанная на рис. 11.1, организована сериями длиной 3. Обратите внимание, что хвост имеет длину, меньшую 3, однако и его записи тоже отсортированы.

7 15 29 8 11 13 I 16 22 31 1 5 12

Рис. 11.1. Файл с сериями длиной 3

Главное в сортировке файлов слиянием - начать с двух файлов, например /i и /г, организованных в виде серий длиной к. Допустим, что (1) количества серий (включая хвосты) в Д. и /г отличаются не больше, чем на единицу; (2) по крайней мере один из файлов fi или fz имеет хвост; (3) файл с хвостом имеет не меньше серий, чем другой файл.

В этом случае можно использовать достаточно простой процесс чтения по одной серии из файлов и /г, слияние этих серий и присоединения результирующей серии длиной 2к к одному из двух файлов gi и g2, организованных в виде серий длиной 2к. Переключаясь между и g2, можно добиться того, что эти файлы будут не только организованы в виде серий длиной 2к, но будут также удовлетворять перечисленным выше условиям (1) - (3). Чтобы выяснить, выполняются ли условия (2) и (3), достаточно убедиться в том, что хвост серий fx и /г слился с последней из созданных серий (или, возможно, уже был ею).

Итак, начинаем с разделения всех п записей на два файла Л и fa (желательно, чтобы записей в этих файлах было поровну). Можно считать, что любой файл состоит из серий длины 1. Затем мы можем объединить серии длины 1 и распределить их по файлам и 2. организованным в виде серий длины 2. Мы делаем А и fz пустыми и объединяем gi и .ga в Д и /г, которые затем можно организовать в виде серий длины 4. Затем мы объединяем Д и /г, создавая и g2, организованные в виде серий длиной 8, и т.д.

Читатель, по-видимому, уже понял, что авторы здесь для простоты изложения материала одинаково обозначают записи и ключи этих записей. Но обратите внимание: в листинге 11.1 предполагается, что записи имеют отдельное поле key (ключ). - Прим. ред.



После выполнения / подобного рода проходов у нас получатся два файла, состоящие из серий длины 2. Если 2 > п, тогда один из этих двух файлов будет пустым, а другой будет содержать единственную серию длиной я, т.е. будет отсортирован. Так как 2 > я при i > logn, то нетрудно заметить, что в этом случае будет достаточно [logn] + 1 проходов. Каждый проход требует чтения и записи двух файлов, длина каждого из них равна примерно п/2. Общее число блоков, прочитанных или записанных во время одного из проходов, составляет, таким образом, около 2п/Ь, где Ъ - количество записей, умещающихся в Одном блоке. Следовательно, количество операций чтения и записи блоков для всего процесса сортировки равняется 0((n\osn)/b), или, говоря по-другому, количество операций чтения и записи примерно такое же, какое требуется при выполнении O(log п) проходов по данным, хранящимся в единственном файле. Этот показатель является существенным улучшением в сравнении с 0(п) проходами, которые требуются многим из алгоритмов сортировки, изучавшихся в главе 8.

В листинге 11.1 показан код программы сортировки слиянием на языке Pascal. Мы считываем два файла, организованных в виде серий длины к, и записываем два файла, организованных в виде серий длины 2к. Предлагаем читателям, воспользовавшись изложенными выше идеями, самостоятельно разработать алгоритм сортировки файла, состоящего из я записей. В этом алгоритме должна logn раз использоваться процедура merge (слияние), представленная в листинге 11.1.

Листинг 11.1. Сортировка слиянием

procedure merge ( к: integer; { длина входной серии } fl, f2, gl, д2: file of recordtype) ;

outswitch: boolean;

{ равна true, если идет запись в gl и false, если в g2 } winner: integer;

{ номер файла с меньшим ключом в текущей записи } used: array[1..2] of integer;

{ usedlj] сообщает, сколько записей прочитано

к настоящему времени из текущей серии файла fj } fin: array[1..2] of boolean;

{ fin[j]=true, если уже закончена серия из файла fj:

либо прочитано к записей, либо достигнут конец файла fj} current: array[1..21 of recordtype;

{ текущие записи из двух файлов }

procedure getrecord ( i; integer);

{ Перемещение по файлу fi, не выходя за конец файла или

конец серии. Устанавливается fin[i]=true, если достигнут конец серии или файла } begin

used[i\:= used[i] + 1; if {used{i]= к) or

(i = 1) and eof(fl) or (i = 2) and eof{f2) then fin[i]:= true else if i = 1 then read(fl, current[l]) else read{f2, current[2]) end; { getrecord }

begin { merge }

outswitch:= true; (первая объединенная серия записывается в gl) rewrite(gl); rewrite{g2) ; reset(fl); reset{f2);





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