AOP_Tom3 (1021738), страница 98
Текст из файла (страница 98)
е. сумму (15) можно уменьшить, если 5, /В-". ф б /В".. Следонательно, мы полу- чим минимальное число операций поиска только при таком условии: Й Й Йт> Вэ Вл, В2 (16) Поскольку минимум обязательно сущестнует, он должен достигаться при в,=,/Х,и/(,/Х,+ . ч- Х,,;), 1<а<р+1 (17) (это единственные значения Вы ..,, Вр,.м удовлетворяющие одновременно (14) н (16)).
Подставив (17) в (15), можно получить несыта простую формулу для общего числа операций поиска, (х/Х~+" + х/Хрэ>)'/и. (18) которую можно сравнить с результатом (Р+1)(Ь1+. +Ар ~ >)/И, получающимся н том случае, если длины всех буферон равны. Как следует из упр. 1.2.3 — 31, выигрыш ранен ( /Х, — /Х,)'/и. ><><ь<Р<1 К сожалению, формула (18) не годится для простого определения оптимальной схемы слияния, как н теореме К (см. упр. 14). Использование сцепления.
В работе М. А. Сне~в, САСИ 6 (1963), 245-248, предложен интересный способ связывания отдельных дорожек, благодаря чему исключается поиск при ныноде. Для реализации такой идеи требуется почти ненообразимый набор программ, управляющих дисками; сама идея применима не только для сортиронки, но и для решения многих других задач.
Поэтому ояа может оказаться несыта полезной для выполнения задач общего назначения. Идея проста. Вместо того, чтобы разместить дорожки последонательно ннутри цилиндрон диска, свяжем их вместе и будем хранить списки свободного пространства по одному для каждого цилиндра. Когда наступит время нынода дорожки информации, запишем ее на текущий цилиндр (на тот, на котором оказался держатель головок), если он не полон. При этом нремя поиска обычно сводится на нет.
Здесь нас полотере>ает ловушка. Дело н том, что мы не можем записывать ссылку на следуюшую дорожку внутри самой дорожки, поскольку необходимая для этого информации н нужный момент неизвестна. (Можно, если это нас устраивает, записать ссылку на предыдущую дорожку н на следующем проходе читать файл н обратном направлении.) Допускается хранение отдельной таблицы адресов снязи для дорожек каждого файла, возможно, частично на самом диске.
Списки свободного пространства можно компактно предстанить с помощью битоных таблиц, в которых 1000 бит указывает занятость или незанятость 1000 дорожек. Пересмотренный вариант прогнозирования. В алгоритме 5.4.6Г показано, как можно предсказать, какой из входных буферов при Р-путевом слиянии освободится первым. Для этого анализируется последний ключ в каждом буфере. В результате можно вьшоанять чтение и вычисление одновременно.
В этом алгоритме используются плавающие входные буфера, не связанные жестко ни с одним из файлов. Таким образом, все буфера могут быть одного размера и можно не использовать каких-либо ухищрений при распределении оперативной памяти для буферов. Ограничения, вытекающие из использования буферов одинакового размера, в настоящее нремя несущественны, поскольку объем оперативной памяти в современных компьютерах не идет ни н какое сравнение с прежними объемами.
Теперь само собой разумеющимся считается выделение буфера объемом в одну дорожку диска. Таким образом, можно считать, что Р серий, которые нужно слить, состоят из последовательности блоков данных, в которой каждый блок (кроме разве что последнего) содержит ровно В записей. Д. Л. Уитлоу (Р. Е. %Ыс!ои) и А. Сассон (А. Бачэоп) разработали интересный алгоритм, названный ими ЯупсБогг [Г 5.
Рагепг 4210961 (1980)), который представляет собой усовершенстованный вариант алгоритма 5.4.6Г и требует использования всего лишь трех буферов размером В вместе со специальным системным буфером (пулом), в котором можно хранвть до РВ записей и РВ указателей. В отличие от этого ноного алгоритма, алгоритм 5.4.6Г требовал 2Р входных буферов и 2 выходных, но не предполагал буферизации указателей. Три буфера для ЯупсБогь объединяются в кольцо.
В процессе слияния компьютер обрабатывает данные в текущем буфере, в то время как входные данные считываются в следующий буфер, а выходные записываются в файл из третьего. Многие модели НМД позволяют записывать и считывать информацию одновременно при обращении к одному и тому же цилиндру. Таким образом, при слиянии можно записывать новые серии на место тех серий, которые считываются, Альтернативный вариант использовать два диска. Тогда с одного из них выполняется чтение, а на другой производится запись.
Если нельзя четко синхронизировать чтение и запись (например, из-за расхождений во времени поиска дорожки), можно включить в кольцо четыре или даже более буферов, как показано на риг. 26 в разделе 1.4.4. Выполнеяие алгоритма ЯупсБон начинается с чтения первого блока каждой серии и передачи этих РВ записей в системный буфер. Каждан запись в системном буфере снязывается с последующей в той серии, которой она принадлежит, кроме последней, у которой еще нет последующей. Наименьший из ключей в последних записях определяет серию, которая первой нуждается в дальнейшей обработке, н мы начинаем считывать второй блок именно этой серии.
Как только второй блок будет считан, начнется слияние. По значению заклк)чительного ключа в этом блоке можно точно определить следующий подходяцгий блок и продолжить таким же способом точно угадывать очередность ввода блоков из исходного файла еще до того, как возникнет необходимость в их обработке.
Алгоритм слияния БупсБогг предполагает обмен каждой записи в текущем буфере со следующей записью па выход, а именно — с записью в системном буфере, имеющей наименьший ключ. Дерево выбора и связи со следующими записями также обнонляются по мере необходимости в процессе такого обмена. Как только будет достигнут конец в текущем буфере, можно "провернуть" кольцо буферов — и буфер считывания станет текущим, буфер записи станет буфером для чтения, а данные из прежнего текущего буфера будут переписьзваться в выходной файл.
Использование нескольких дисков. Первые накопители на магнитных дисках были устройствами внушительных габаритов и веса, но со временем они стали намного меньше, легче, а главное — дешевле, но емкость их намного возросла. Это совершенно естественно привело к тому, что многие разработчики обратили внимание на создание специальных алгоритмов для ранее немыслимых комплексов из 5, 10 или даже 50 совместно работающих НМД. Один из способов использования множества дисков — применение технологии разделения данвмт (в1з)г зггзрбгу) для больших файлов.
Предположим, в нашем распоряжении имеется Р НМД, пронумерованных О, 1, ..., Р— 1, и рассмотрим файл, который состоит из Е блоков аеа1... аь ь Разделение этого файла на Р дисков означает, что блок а, записывается на диск под номером у' шоб Р. Следовательно, на диске 0 хранятся блоки аеаразр..., на диске 1 — а1ап ыазр~.з... и т. д. При такой организации можно выполнять Р операций чтения или записи одновременно в группах из Р блоков аеаз... ав ы апапьз... агп — м ..., которые называются суперблоками. Отдельные блоки в каждом суперблоке должны находиться на соответствующих цилиндрах различных дисков, что обеспечит одинаковое время поиска на каждом устройстве. Теперь мы сможем работать, как если бы в нашем распоряжении был один-единствевный диск с этими блоками данных и буфера объемом РВ, но операции ввода и вывода выполнялись в Р раз быстрее. Благодаря такой организации разлеления данных получается довольно изящный вариант усовершенствования сортировки при выполнении 2-путевого слияния или (в общем случае) всегда, когда необходимо привести в соответствие записи с равными ключами в двух файлах, упорядоченных по ключам.
Предположим, что блоки аз азат... первого файла разделены между Р дисками, как описано выше, но блоки деЬзЬз... другого файла разделены в обратном порядке, т. е. блок Ь хранится на диске (Р— 1 — 1) шос) Р. Например, если Р = 5, то блоки а; находятся соответственно на дисках О, 1, 2, 3, 4, О, 1,..., а блоки Ь„у' > О, находятся на дисках 4, 3, 2, 1, О, 4, 3, .... Пусть а, — последний ключ в блоке а,, а бу — последний ключ в блоке Ь . Проанализировав блоки и и д, можно предсказать нужный порядок считывания данных из этих блоков.
Например, эта последовательность может иметь вид аеЬее,азЬз аза45зозав агазЬзЬзЬз ЬвЬгЬзЬзЬ|о При Р = 5 блоки находятся соответственно па дисках 04123 34201 23104 32104 и, если считывать их по пять одновременно, можно осуществлять ввод безо всяких помех с дисков (0,4,1,2,3), (3,4,2,0,1), (2,3,1,0,4), (3,2,1,0,4), .... При этом никогда не возникнет конфликт вследствие попытки прочесть одновременно два блока с одного и того же устройства! В общем случае, имея Р дисков, можно бесконфликтно считывать Р блоков сразу, поскольку при некотором Ь первая группа будет иметь )с блоков ае...
аь 1 на дисках от О до Ь вЂ” 1, а Р— )с блоков Ье... Ьр на дисках от Р— 1 до Ь. Далее можно продолжать в том же духе, но с дисками, номера которых сдвигаются циклически на )с. Этот трюк хорошо известен карточным фокусникам, которые называют его принципом Гилдрегаа. Трюк изобретен в 60-х годах Норманом Гилбретом (Хат|пап СВЪгеа|Ь) ~сзс Магбп Сагйпег, Ма|йетабса! Мак|с ЯЛо|г (Хен Ъогй~ Кпор?, 1977), СЬар|ег 7; ?1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
