Структуры данных и алгоритмы (1021739), страница 82
Текст из файла (страница 82)
сначала мы читаем в буфер первый блок файла, затем заменяем его на второйблок, который записывается в тот же буфер, и т.д.Теперь нетрудно понять концепцию, которая лежит в основе правил чтения файлов в языке Pascal. Каждый файл хранится в виде определенной последовательностиблоков; каждый такой блок содержит целое число записей. (Память будет использоваться нерационально, если хранить части одной и той же записи в разных блоках.)Указатель считывания всегда указывает на одну из записей в блоке, который в данный момент находится в буфере.
Когда этот указатель должен переместиться на запись, отсутствующую в буфере, настало время прочитать следующий блок файла.Аналогично, процесс записи файла в языке Pascal можно рассматривать как процесс создания файла в буфере. Когда записи "записываются" в файл, фактически онипомещаются в буфер для этого файла — непосредственно вслед за записями, которыеуже находятся там.
Если очередная запись не помещается в буфер целиком, содержимое буфера копируется в свободный блок вторичной памяти, который присоединяется к концу списка блоков для данного файла. После этого можно считать, чтобуфер свободен для помещения в него очередной порции записей.Стоимость операций со вторичной памятьюПрирода устройств вторичной памяти (например, дисководов) такова, что время,необходимое для поиска блока и чтения его в основную память, достаточно велико всравнении со временем, которое требуется для относительно простой обработки данных, содержащихся в этом блоке. Допустим, например, что у нас имеется блок из1000 целых чисел на диске, вращающемся со скоростью 1000 об/мин.
Время, которое требуется для позиционирования считывающей головки над дорожкой, содержащей этот блок (так называемое время установки головок), плюс время, затрачиваемое на ожидание, пока требуемый блок сделает оборот и окажется под головкой(время ожидания ), может в среднем составлять 100 миллисекунд. Процесс записиблока в определенное место во вторичной памяти занимает примерно столько жевремени. Однако за те же 100 миллисекунд машина, как правило, успевает выполнить 100 000 команд. Этого времени более чем достаточно, чтобы выполнить простуюобработку тысячи целых чисел, когда они находятся в основной памяти (например,их суммирование или нахождение среди них наибольшего числа).
Этого времени может даже хватить для выполнения быстрой сортировки целых чисел.Оценивая время работы алгоритмов, в которых используются данные, хранящиеся в виде файлов, нам придется, таким образом, в первую очередь учитывать количество обращений к блокам, т.е. сколько раз мы считываем в основную память или записываем блок во вторичную память. Такая операция называется доступом (или обращением) к блоку. Предполагается, что размер блока фиксирован в операционнойсистеме, поэтому у нас нет возможности ускорить работу алгоритма, увеличив размерблока и сократив тем самым количество обращений к блокам. Таким образом, меройкачества алгоритма, работающего с внешней памятью, является количество обращений к блокам. Изучение алгоритмов, работающих с внешней памятью, мы начнем срассмотрения способов внешней сортировки.312ГЛАВА 11.
СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИ11.2. Внешняя сортировкаСортировка данных, организованных в виде файлов, или — в более общем случае — сортировка данных, хранящихся во вторичной памяти, называется внешнейсортировкой. Приступая к изучению внешней сортировки, сделаем предположение,что данные хранятся в Pascal-файле. Мы покажем, как алгоритм сортировки слиянием позволяет отсортировать файл с п записями всего лишь за O(logn) проходов через файл; этот показатель намного лучше, чем О(п) проходов, которые требовалисьалгоритмам, изучавшимся в главе 8. Затем мы рассмотрим, как использовать определенные возможности операционной системы по управлению чтением и записьюблоков, что может ускорить сортировку за счет сокращения времени "бездействия"компьютера (периоды ожидания, пока блок будет прочитан в основную память илизаписан из основной памяти во внешнюю).1'.
,Сортировка слияниемГлавная идея, которая лежит в основе сортировки слиянием, заключается в том,что мы организуем файл в виде постепенно увеличивающихся серий, т.е. последовательностей записей гь ... ,rk, где ключ rt не больше, чем ключ ri+1, I < i < k.1 Мы говорим, что файл, состоящий из r l f ... ,гт записей, делится на серии длиной h, еслидля всех i > О, таких, что Ы < т и rt((-i)+1, rt(j_1)+2, ... , гы является последовательностью длиной k.
Если т не делится нацело на k, т.е. т = pk + q, где q < k, тогда последовательность записей rm_?+1, rm_e+2, — > rm> называемая хвостом, представляетсобой серию длиной q. Например, последовательность целых чисел, показанная нарис. 11.1, организована сериями длиной 3.
Обратите внимание, что хвост имеет длину, меньшую 3, однако и его записи тоже отсортированы.7 15 298 11 13|Рис. 11.1. Файл с сериями длиной 316 22 31' ".''|••5 12 ~•'. .;.'..'Главное в сортировке файлов слиянием — начать с двух файлов, например fl и /2,организованных в виде серий длиной k. Допустим, что (1) количества серий(включая хвосты) в Д. и /2 отличаются не больше, чем на единицу; (2) по крайнеймере один из файлов fi или /2 имеет хвост; (3) файл с хвостом имеет не меньше серий, чем другой файл.В этом случае можно использовать достаточно простой процесс чтения по однойсерии из файлов Д и /2, слияние этих серий и присоединения результирующей сериидлиной 2k к одному из двух файлов gi и g2, организованных в виде серий длиной 2k.Переключаясь между g\ и g2, можно добиться того, что эти файлы будут не толькоорганизованы в виде серий длиной 2k, но будут также удовлетворять перечисленнымвыше условиям (1) - (3).
Чтобы выяснить, выполняются ли условия (2) и (3), достаточно убедиться в том, что хвост серий Д и /2 слился с последней из созданных серий(или, возможно, уже был ею).Итак, начинаем с разделения всех п записей на два файла Д и Д. (желательно,чтобы записей в этих файлах было поровну). Можно считать, что любой файл состоит из серий длины 1. Затем мы можем объединить серии длины 1 и распределить их по файлам gi и g2, организованным в виде серий длины 2. Мы делаем f i иfz пустыми и объединяем gi и g2 в Д и /2, которые затем можно организовать в виде серий длины 4. Затем мы объединяем Д и f2, создавая gi и g2, организованные ввиде серий длиной 8, и т.д.1Читатель, по-видимому, уже понял, что авторы здесь для простоты изложения материалаодинаково обозначают записи и ключи этих записей.
Но обратите внимание: в листинге.11.1предполагается, что записи имеют отдельное поле key (ключ). — Прим. ред.11.2. ВНЕШНЯЯ СОРТИРОВКА313После выполнения i подобного рода проходов у нас получатся два файла, состоящиеиз серий длины 2'. Если 2' > п, тогда один из этих двух файлов будет пустым, а другойбудет содержать единственную серию длиной п, т.е. будет отсортирован. Так как 2' > ппри i > logn, то нетрудно заметить, что в этом случае будет достаточно [logn] + 1 проходов. Каждый проход требует чтения и записи двух файлов, длина каждого из них равна примерно п/2.
Общее число блоков, прочитанных или записанных во время одногоиз проходов, составляет, таким образом, около 2п/Ь, где Ъ — количество записей, умещающихся в одном блоке. Следовательно, количество операций чтения и записи блоковдля всего процесса сортировки равняется О((п logn)/b), или, говоря по-другому, количество операций чтения и записи примерно такое же, какое требуется при выполненииO(log п) проходов по данным, хранящимся в единственном файле.
Этот показатель является существенным улучшением в сравнении с О(п) проходами, которые требуютсямногим из алгоритмов сортировки, изучавшихся в главе 8.В листинге 11.1 показан код программы сортировки слиянием на языке Pascal.Мы считываем два файла, организованных в виде серий длины k, и записываем двафайла, организованных в виде серий длины 2k.
Предлагаем читателям, воспользовавшись изложенными выше идеями, самостоятельно разработать алгоритм сортировки файла, состоящего из п записей. В этом алгоритме должна logn раз использоваться процедура merge (слияние), представленная в листинге 11.1.„ • _.-• :.^•••••••\ ' < ••-.- iЛистинг 11.1. Сортировка слиянием'{-: •' . - . :'-procedure merge ( k: integer; { длина входной серии }fl, f2, gl, g2: file of recordtype);varoutswitcn: boolean;{ равна true, если идет запись в gl и false, если в g2 }winner: ;Lnteger;{ номер файла с меньшим ключом в текущей записи }used: array[1..2] of integer;{ used[j] сообщает, сколько записей прочитанок настоящему времени из текущей серии файла fj }fin: array[1..2] of boolean;{ Пл[j]=true, если уже закончена серия из файла fj:либо прочитано k записей, либо достигнут конец файла fj}current: array[1..2] of recordtype;{ текущие записи из двух файлов }procedure getrecord ( i: integer);{ Перемещение по файлу fi, не выходя за конец файла иликонец серии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
