Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 85
Текст из файла (страница 85)
Заметим, что (а) не является на самом деле ограничением, так как имеется только одна выводная лента. Кроме того, объем ввода равен объему вывода, так что читается в среднем только одна лента в любой данный момент времени; если условие (Ъ) не выполняется, то обязательно должны быть периоды, когда ввод вообще не происходит. Следовательно, для того чтобы минимизировать время слияния, достаточно поддерживать вьпюдную ленту в рабочем состоянии.
Желаемый эффект дает важный метод, называемый предсказанием или прогновирова1шем (1Огесавс!п8). Во время выполнения Р-путевого слияния обычно имеется Р шекущих буферов ввода, которые используются как источники данных; одни из них заполнены больше других в зависимости от того, какая часть данных в ннх уже просмотрена. Если все они опустошатся примерно в одно и то же время, то, прежде чем продолжить работу, нам придется выполнить много операций чтения, если только мы не предпримем нужных мер заранее, К счастью, всегда можно сказать, какой буфер первым станет пустым, просто посмотрев на последнюю запись в каждом буфере. Буфер, последняя запись которого имеет наименьший ключ, обязательно станет первым пустым буфером независимо от значений каких-либо других ключей, так что мы всегда Знаем, какой файл послужит причиной следующей команды ввода.
Алгоритм г раскрывает этот принцип в деталях. Алгоритм Р (Прогнозирование с плавающи ии буферами). Этот алгоритм (рис. 83) управляет буферизацией во время Р-путевого слияния длинных файлов при Р > 2. Допустим, что вводные ленты и файлы пронумерованы так: 1, 2,..., Р. В алгоритме используются 2Р буферов ввода, 1 Гц,..., 1 [2Р), два буфера вывода, О(03 и О Ш, н следующие вспомогательные массивы. А Ц3, 1 < у <2Р: О, если в буфер 1(Я можно вводить данные; 1 — в противном случае ВЫ, 1 <1 < Р: Буфер, содержащий последний прочитанный блок из файла 1 С Ы, 1 < 1 < Р: Буфер, используемый в настоящий момент для ввода из файла ( 1П), 1<1 < Р: Последний ключ, прочитанный нз файла 1 ЗИ,1<З < 2Р: Буфер, который следует использовать, когда 1(уЗ опустошится В описываемом виде алгоритм никогда не остановит работу. Подходящий способ его "выключения" обсуждается ниже.
Рис. ББ. Прогнозироваин» с плававшими буферами. Р1. [Начальная установка.] Прочитать первый блок с ленты 1 в буфер 1[с], установить АН3 с- 1, А[Р+ с3 с — О, В[с] с — с, С[с] с — с и установить |.[с] равным ключу последней записи в 1[с] при 1 < с < Р. Затем найти т, такое, что 1.[т3 = ш[п(1 [1],..., 1 [Р]), и установить С с- О, )с +- Р + 1. Начать чтение с ленты т в буфер 1[А]. Р2. [Слияние,] Сливатьзаписиизбуферов1[С[1]3,...,1[С[Р]] вО[И,покаО[с] не заполнится. Если во время этого процесса какой-нибудь буфер ввода, скажем 1[С[с]], станет пустым, а 0[1] еще не будет заполнен, то установить А[С[с]] с — О, С[с] с- В[С[с]] и продолжать слияние.
РБ. ]Ввод-вывод завершен.] Ожидать, пока не завершится предыдущая операция чтения (или чтения/записи). Затем установитьА[А] с- 1, В[В [т]3 с- Й, В[т3 с- А и установить 1, [тл3 равным ключу последней записи в 1 [А]. У4. [Прогнозирование.] Найти т, такое, что 1[т3 = пип(1Ш,..., 1[Р3], и найти А, такое, что А [А] = О. РВ.
]Чтение~запись.] Начать чтение с ленты т в буфер 1 [А] и выполнить запись из буфера 0 [1] на выводную ленту, затем положить С с- 1 — С н вернуться к Г2. А В примере на рис. 84 показало, как работает метод прогнстснрования при Р = 2 в предположении, что каждый блок на ленте содержит только две записи. Здесь представлено содержимое буферов ввода во все моменты, когда мы достигаем начала шага Е2. Алгоритм Р„в сущности, образует Р оч»р»д»й буферов, где С[1] — на начало с й очереди, В[с] — на ее конец, Б [Я указывает на преемника буфера 1 [Я; этим указаниям на рис.
84 соответствуют стрелки. Строка 1 отражает состояние дел после начальной установки. Для каждого вводного файла есть один буфер„и еще один блок читается нз файла 1 (так как 03 < 05). Строка 2 показывает положение вещей после того, как слит первый блок: мы выводим блок, содержащий ~Я 02, и вводим следующий блок из файла 2 [так как 05 < 09). Заметим, что в строке 3 три из четырех буферов ввода, по сути дела, предоставлены файлу 2, так как мы выполняем чтение из этого файла и в его очереди уже есть полный буфер и частично заполненный буфер. Этот механизм плавающих буферов является важной чертой Содержимое файла ! 01 ОЗ 04 09 И 12 10 1б Содейжимсе файла 2 02 05 Об 07 Об !О 12 14 Затем исходные данные читавтсн из 1-го файла Номер строки Буфера файла 1 -р(о~ Оз)~ 2 з -~~ ООД4- -Э~ 02 )Е- з б -й(п 12)4- Буфера Файла 2 -и) 02 05 ~~ -й[ 00)4- 2-го Файла 2-го файла 1-го файла 2-го Файла 1-го файла 2-го Файла Рис.
84. Очереди буферов в соответствии с алгоритмом Г. алгоритма Р, поскольку мы ие смогли бы продолжить работу в строке 4, если бы в строке 3 выбрали файл 1 для ввода вместо файла 2. Чтобы доказать работоспособность алгоритма и, мы должны проверить выполиеиие двух условий во время реализации алгоритма: !) всегда имеется свободный буфер (т.
е. всегда можио найти и на шаге Р4); й) если буфер ввода исчерпывается во время слияния„то его преемник уже присутствует в памяти (т. е, 3[СИ] иа шаге Р2 имеет осмысленное значение). Допустим, что условие (1) ие выполняется, т. е, все буфера запяты в некоторый момент, когда мы достигаем шага Р4. Каждый раз, когда мы приходим к зтому шагу, суммарный объем необработанных даииых во всех буферах составляет ровно Р емкостей буфера, т. е, данных ровно столько, сколько нужно для заполнения Р буферов,. ибо данные вводятся и вывсдятся с одинаковой скоростью. Некоторые буфера заполиеиы лишь частично, однако для каждого файла частично заполнен максимум одии буфер, так что всего таких буферов ие более Р.
По предположеиию все 2Р буферов заняты, так что по меиыпей мере Р из иих должны быть заполиеиы целиком. Это может случиться, только если Р буферов полны и Р пусты, иначе мы бы имели слшпком много данных. Но максимум один буфер может быть одновременно пуст и иедоступеи; следовательио, условие (!) ие может ие выполняться. Допустим, что условие (И) ие выполняется, т. е. для некоторого файла в памяти иет необработанных записей, ио текущий буфер вывода еще ие полон. Согласио принципу прогнозирования пужио иметь ие более одиого блока даииых лля всех остальных файлов, так как мы ие читаем блок из файла, если этот блок ие потребуется прежде, чем будут исчерпаны буфера какого-нибудь другого файла.
Таким образом, общее число необработанных записей составляет максимум Р— 1 блоков; добавление иеполиого буфера вывода дает привод к менее чем Р буферным емкостям данных в памяти; значит, получеио противоречие. Этот анализ подтверждает работоспособиость алгоритма Г; ои также показывает, что возможны особые ситуации, при которых алгоритм едва-едва избегает крушения. Нами здесь не упомянута еще одна важная тонкость, касающаяся возможного равенства ключей; это обсуждается в упр. 5. [См. также упр. 4, в котором рассматривается случай Р = Ц Один из способов изящного завершения алгоритма г' состоит в присвоении 5~т) значения оо на шахе Г3, если только что прочитанный блок был последним в серии. (Конец серии всегда некоторым особым образом помечается.) После того как будут прочитаны все данные во всех файлах, мы, в конце концов, обнаружим на шаге Г4, что все Е равны со„тогда обычно можно начать чтение первых блоков следующих серий в каждом файле, выполняя начальную установку для следующей фазы слияния по мере вывода последних Р + 1 блоков.
Таким образом, можно поддерживать полную скорость работы выводной ленты, осуществляя чтение в любое время не более одной ленты. 1!сключение нз этого правила встречается на шаге Р1, где было бы полезно читать сразу несколько лент, чтобы обеспечить возможность начать работу; но обычно шаг Г1 можно организовать так, чтобы он совмещался с предыдущей частью вычислений.
Идея просмотра последней записи кахсдого блока, чтобы предсказать, какой буфер первым станет пустым. была высказана в 1953 году Ф. Э. Гольбертон (Г. Е. Но1- Ьеггоп). Сам метод впервые был опубликован в работе Б. Н. Гг1епб, 3АСМ 3 (1956), 144 — 145, 165. В этом довольно сложном алгоритме использовалось 3Р буферов ввода и каждому файлу ввода предназначалось по трн буфера. Алгоритм Р несколько более совершенен, поскольку в нем используются плавающие буфера, что позволяет, таким образом, любому одному файлу потребовать сразу даже Р+1 буферов ввода, хотя всего требуется не более 2Р буферов. Слияние с менее чем 2Р буферами обсуждается в конце этого раздела. Некоторые интересные подходы к совершенствованию алгоритма Г рассматриваются в разделе 5.4.9.
Сравнительный анализ схем слияния. Используем теперь наши знания о лентах и слиянии, чтобы сравнить эффективность различных схем слияния, рассмотренных в разделах 5.4.2-5.4.5. Будет весьма поучительно проанализировать детально каждый метод в применении к одному и тому же примеру. Рассмотрим поэтому сортировку файла, каждая запись которого содержит 100 символов, причем в памяти для записи данных доступно 100,000 символьных ячеек (не считая места для программы, ее вспомогательных переменных и сравнительно небольшого пространства, необходимого для ссылок в дереве выбора). Исходные данные расположены на лепте в случайном порядке блоками по 5 000 симвочов, н результат должен получиться в том же формате.
В нашем распоряжении имеется пять рабочих НМЛ в дополнение к устройству, на котором находится вводная лента. Общее число сортнруемых записей — 100,000, но эта информация алгоритму сортировки заранее не известна. В диаграмму А (здесь и далее см. вкладку) сведены те операции, которые выполняются, когда к нашим данным применяется десять различных схем слияния. Обратившись к этой важной иллюстрации, очень полезно вообразить, что вы наблюдаете за реальной сортировкой: медленно просматривайте каждую строку слева направо, мысленно представляя себе шесть лент, осуществляющих чтение, запись, перемотку и/нли обратное чтение, квк указано на диаграмме.
В течение Р-путевого слияния вводные ленты будут находиться в движении в 1~Р раз реже, чем выводная лента. Заметим, что на диаграмме А предполагается, что, когда пер- воначальная вводная лента полностью прочитана (и перемотана, чтобы ее убрать), умелый оператор снимает ее и заменяет рабочей лентой за 30 с. В примерах 2-4 это и есть время критического пути, когда комш,ютер в бездействии ожидает оператора. Но в остальных примерах операция снятия и установки лент совмещена с другой работой. (На диаграмме А по горизонтали указано время в минутах.) Пример 1.
Сбалансированное слияние с прямым чтением. Напомним описание задачи: записи имеют длину 100 символов, внутренней памяти достаточно для одновременного храпения 1 000 записей и каждый блок вводной ленты содержит 5 000 гимвопов (50 записей). Всего имеется 100,000 записей (что равно 10,000,000 символов нли 2 000 блоков). Мы ничем не связаны в выборе размера блоков для промежуточных файлов. Прн шестиленточном сбалансированном слиянии используется трехпутевое слияние, так что техника алгоритма г требует 8 буферов; можно, следовательно, использовать блоки, содержащие по 1000/8 = 125 записей (или 12 500 символов). Проход начального распределения может использовать выбор с замещением (алгоритм 5.4.1Н), и, чтобы поддерживать непрерывную работу лент, будем использовать два буфера ввода по 50 записей плюс два буфера вывода по 125 записей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
