AOP_Tom1 (1021736), страница 75
Текст из файла (страница 75)
Так как 5 является конечным множеством, для некоторого г ( /с должно выполняться условие Ь = Ьы Но тогда предполагается, что выполняется условие Ьь с Ьз+ы а это противоречит свойству (11). Для эффективной реализации рассмотренного процесса на компьютере необходимо организовать выполнение перечисленных выше действий, т. е. поиск объектов без предшественников, а также их удаление из множества. На окончательный внд алгоритма также повлияют заданные характеристики операций ввода и вывода. В общем случае программа должна уметь воспринимать символьные имена объектов н обрабагывать гигантские множества, размер которых может даже превышать размер оперативной памяти компьютера.
Однако обсуждаемые здесь основные идеи могут легко затеряться среди таких усложнений. Поэтому более подробно методы эффективной обработки символьных данных описываются в главе 6, а задачу управления болылими сетями читателю предлагается обдумать самостоятельно в качестве интересного упражнения. Далее предположим, что сортируемые объекты пронумерованы от 1 до и в произвольном порядке. Вводная часть программы будет находиться на накопителе на магнитной ленте 1.
Каждая магнитная зались содержит 50 лар чисел, где пара (з,й) означает, что объект г предшествует объекту Ь. Однако первая пара выглядит как (О,п), где п — это количество объектов. Ввод завершается парой (О, 0). Предположим, что и и все пары помещаются в памяти компьютера, а потому необязательно проверять наличие свободного места в памяти во время ввода этих данных.
Выводиться объекты будут уже в отсортированном порядке на накопитель на магнитной ленте 2, причем за ними будет следовать значение О. 1 3 3 4 $ б 7 3 сопят[31 тсв[ь] вахт 3ПС вахт Рис. 8. Компьютерное представление показанной иа рис. 6 последовательности элементов с отношениями (18). Например, поток ввода может содержать следующие объекты с такими отношениями между ними: 9<2, Зс7, 7 ч5, 5 с8, 8-сб, 4.чб, 1чЗ, 7<4, 9ч5, 2ч8.
(18) Здесь необязательно приводить какие-то дополнительные отношения для характеристики искомого частичного упорядочения. Например, дополнительные отношения типа 9 с 8 (которые можно вывести из отношений 9 м 5 и 5 ~ 8) можно беэ какого-либо влияния на конечный результат опустить или добавить во входной поток данных. В общем случае необходимо указать только те отношения, которые соответствуют стрелкам на диаграмме, показанной на рис. б. В приведенном ниже алгоритме используется последовательно упорядоченная таблица Х[ц, Х [21, ..., Х[в), в которой каждый узел Х[к) имеет вид Здесь СООИТ [к) обозначает количества пряммх предшественников объекта к (т, е, количество отношений у' -ч к во входном потоке данных), а ТОР[к) — связь с началом списка прямых потомков объекта к.
Последний список содержит элементы в формате где ЯОС вЂ” прямой потомок объекта к и йЕХТ вЂ” следующий элемент списка. Для демонстрации этих условных обозначений на рис. 8 схематически показано содержимое памяти, соответствующее входному потоку данных (18). Используя такую организацию памяти, нетрудно создать искомый алгоритм. Для этого следует вывести узлы, в которых значение поля СООМТ равно нулю, и на единицу уменьшить значения полей СООМТ для всех потомков таких узлов. Уловка здесь заключается в том, чтобы избежать "поисЫ' узлов, в которых значение поля СООМТ равно нулю, и это можно выполнить за счет организации очереди, содержащей такие узлы.
Связи для этой очереди хранятся в поле СООМТ, которое уже выполнило свае назначение. Для ясности в приведенном ниже алгоритме обозначение ЦЕ1ИК [к] используется вместо СООИТ [к], когда это поле больше не применяется для хранения значений счетчика.
Алгоритм Т (Топологическол сортдпроека). В этом алгоритме в качестве входного потока используется последовательность отношений 3 .ч к, обозначающих, что объект у предшествует объекту й в некотором частичном упорядочении при условии, что 1 < у, (г < и. Выходной поток состоит из множества п объектов, расположенных в линейном порядке. При этом используются следующие внутренние таблицы: Ц1.1ИК[03, СООИТ[Ц = Ц1.1ИК[Ц, СООИТ[23 = Ц1.1ИК[23, ..., СООМТ[п] = Ц1.1ИК[п3; ТОР[13, ТОР[23, ..., ТОР [п3; пул с одним узлом для каждого отношения входного потока и с указанными выше полями ЯОС и ИЕХТ; переменная связи Р, которая используется для ссылки на узлы в пуле; целочисленные переменные Р и й, применяемые для ссылок на начало и конец очереди, связи которых находятся в таблице ЦЕ1ИК; и, наконец, переменная И, позволяющая подсчитать количество объектов, которые необходимо поместить в выходной поток.
Т1. [Инициализация.[ Ввести значение и. Установить СООМТ [к] < — 0 и ТОР [Х] < — Л для 1 < к < и. Установить и ~- и. Т2. [Следующее отношение.[ Получить отношение у ч /с из входного потока. Если входной поток исчерпан, перейти к шагу Т4. ТЗ.[Запись отношения.[ Увеличить на единицу значение СООИТ[к] Установить Р ~ ХЧХП., ЯОС(Р) +- й, ИЕХТ(Р) ~- таИЛ, ТОР[)] ~- Р. [Это операция (8).) Вернуться к шагу Т2. Т4. [Поиск нулей.[ (В этом месте завершается ввод, и входной поток (18) теперь имеет понятный для компьютера вид, представленный на рис. 8.
Следующий шаг заключается в инициализации очереди выходного потока, который связан с помощью поля ЦЕТИК.) Установить Н ~- 0 и ЦЕ1ИК [03 +- О. Для 1 < к < и проверить значение СООИТ [к] и, если оно равно нулю, установить ЦЕ1ИК [К] +- к и й < — Й. После выполнения этого действия для всех к установить Р < — ЦЕ1МК [03 (теперь оно будет содержать первое значение й, для которого СООИТ[к] равно нулю) . ТЯ.
[Вывод начала очереди.] Вывести значение Р. Если Р = О, перейти к шагу Т8, в противном случае установить И <- И вЂ” 1 и установить Р <- ТОР[Р3. (Так как таблицы ЦЕ1ИК и СООИТ перекрываются, получим ЦЕ1ИК[й] = О. Следовательно, условие Р = 0 выполняется, когда очередь пуста.) Тб. [Удаление отношений.) Если Р = Л, перейти к шагу Т7. В противном случае уменьшить на единицу значение СООИТ[ЯОС(Р)], а если оно уже равно нулю, установить Ц1.1ИК[83 + — ЯОС(Р) и К +- ЯОС(Р). Установить Р < — ИЕХТ(Р) и повторить этот шаг. (Таким образом удаляем из системы все отношения вида Р -ч к для некоторога к и располагаем новые узлы в очереди, когда все их предшественники уже выведеньь) ТТ.
[Удаление из очереди.) Установить Р < — Ц1.1ИК [Р3 и вернуться к шагу Т5. ТЯ. [Конец процесса.) Прекращение работы алгоритма. Если И = О, получим в ре. зультате искомое "топологическое упорядочение" пронумерованных объектов, Программа Т (Топалогическол сортировка). В этой программе (рис. 9) нужно учесть следующие равенства: г16 = Н, г15 г— я указатель буфера, г14 я А, г13 = ] и Е, г12 = АУА1Е и Р, г11 = Р, ТОР [2] = Х + Д4: 5), СОПИТ [А] = ОЫМК [Ц = Х+ А(2: 3).
01 е БУФЕРИЗАЦИЯ И ОПРЕДЕЛЕНИЕ ПОЛЕЙ ОЯ СОПИТ ЕОО 2:3 Определение символьных 03 ОБ1МК ЕОО 2:3 имен полей. 04 ТОР ЕОО 4: Б бб 30С ЕОО 2:3 дб НЕХТ ЕОО 4:Б 07 ТАРЕ1И ЕОО 1 бб ТАРЕООТ ЕОО 2 Ввод с ленты 1. Вывод на ленту 2 за которыми следует нуль. В противном случае Н пронумерованных объектов не будут выведены из-за того, что они образуют замкнутую петлю, а это нарушает гипотезу о частичном упорядочении. (В упр.
23 рассмотрен алгоритм печати содержимого такой петли.) $ Читателю наверняка будет полезно попробовать вручную применить этот алгоритм для входного потока (18). Алгоритм Т демонстрирует прекрасное взаимодействие между методами организации последовательной и связанной памяти. Последовательная память используется для основной таблицы Х[1], ..., Х[п], которая содержит объекты СОПИТ[А] и ТОР[А], поскольку на шаге ТЗ предстоит ссылаться на "произвольно выбранные" части этой таблицы. (Однако, если входной поток является символьным, для более быстрого поиска следует использовать другой тип таблицы, который описывается в главе 6.) Связанная память применяется для таблиц, в которых "один объект непосредственно следует за другим" (1пппе8!аАе эпссеэеогэ), так как во входном потоке зти объекты никак не упорядочены.
Очередь ожидающих вывода узлов хранится внутри последовательной таблицы, связывая, таким образом, узлы в порядке их вывода. Для этого связывания вместо адресов используется индекс таблицы. Иначе говоря, если Х[А] — начало очереди, получим Р = А вместо Р = 1.0С(Х[А]). Операции обработки очереди, используемые на шагах Т4, Тб и Т7, не идентичны оперениям (14) и (17), так как в данном случае используются преимущества особых свойств очереди. Во время выполнения этой части алгоритма никакие узлы не придется создавать или возвращать в свободное пространство памяти. При программировании алгоритма Т на языке ассемблера компьютера И1Х следует учесть несколько интересных особенностей.
Так как в данном алгоритме в таблице не предпринимается никаких удалений (поскольку не требуется освобождать память для ее последующего использования), операция Р ~ АУА1Е может быть выполнена чрезвычайно просто, т. е. так, как показано ниже, в строках 19 и 32. В такой ситуации не потребуется содержать связанный пул памяти, а новые узлы можно выбирать последовательно.
Ввод и вывод данных в программе предполагается выполнить с магнитной ленты согласно упомянутым выше соглашениям, но для упрощения кода в данном случае опущена буферизация. Читатель вряд ли столкнется с какими-либо трудностями при чтении этого кода, поскольку код полностью соответствует алгоритму Т. Здесь также показано, насколько эффективно может быть организовано использование индексных регистров, что является важным аспектом обработки связанной памяти. Рис. 9.
Топологическая сортировка. Буферная область. Метка конца буфера. 1 1 и+1 и+1 и+1 1 1 си+ 5 пс+5 Ь Ь вЂ” 1 Ь вЂ” 1 Ь вЂ” 1 ОУ ВОРРЕЕ 10 11 « ФАЗА 1З ТОРЯОЗТ 1В 11 1Н 15 1В 17 1В 1У ЗВ В1 2Н ВВ ВВ ВВ ЯВ ВВ В7 ВВ ЗН ВУ ВО ВХ ВЗ ВВ В1 ВВ Вб В7 ВВ ОЗХО «+100 СОИ -1 ВВОДА ХИ ВОРРЕН(ТАРЕХИ) ВВОЗ «(ТАРЕТИ) 106 ВОРРЕН+1 ЕИТ4 0,6 ЗТХ Х,4 РЕС4 1 14ИИ «-2 ЕИТ2 Х,б ЕИТЗ ВОРРЕЗ+2 1.03 0,5 ВЗР ЗР ВЗХ 4Р 1И ВОРРЕЗ(ТАРЕ1И) ]ВОЯ «(ТАРЕХМ) ЕИТЯ ВОРРЕЗ 1ИР 2В 104 1,5 ЬЗА Х,4(СООИТ) ТИСА 1 ЯТА Х,4(СООИТ) ХИС2 1 ЮА Х,З(ТОР) ЯТА 0,2(ИЕХТ) ЯТ4 0,2(ЯОС) ЯТ2 Х,З(ТОР) 1ИС5 2 Л(Р 2В н,и.сс«с~ °,«.ю блок ленты; дождаться завершения. И «- и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
