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