1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 5
Текст из файла (страница 5)
Мы не торопимся ввести новую величину для результата очередного оператора Я, а смотрим на величины, обозначающие реаультаты операторов, стоящих выше. Что значит, что величина и, которая была реаультатом оператора В, еще не осзободилась7 Это значит, что ниже оператора Я есть еще один оператор, Т, имеющий и своим аргументом. Достаточно ли точное это определение7 Легко можно догадаться, что нет. Путем комбинирования возможных случаев получим такие варианты выработки и использования величины и по отношению к оператору Я гл. ь содержательныи АЯАлиз 3АдАчи 22 (для четкости будем полагать, что никаких других использований величины и, кроме явно покааанных, в программе нет)1 Программа Программа Программа Программа о г=., Т'.
а:= У'(г) Ь гх:=... л'. г:=... Т: а:= Г(о) Лг г г=... ТЧ а:= Г(г) Ь: х:=... Т: а:= г"(о) Тя о:=... Т". а:= Г(г) ог х:= П: гг=... Ь". х:.=... := г'(о) случай б) случай в) случай г) случай а) Посмотрев на эти картинки, мы заключаем, что единственным условием того, что величина и занята по отношению к оператору Я, является такая ситуация, что Я находится между (в смысле положения в программе) выработкой р (оператор гг) и использованием р (оператор Т);.при этом между Я и Т нет оператора, вырабатывающего ш Получается, что оператор Ю стоит как бы на пути передачи значения от Л к Т. Эту ситуацию можно сделать более наглядной, если изобрааигь этот путь величины р в виде линии, соединяющей результат оператора Л и аргумент оператора Т1 Если допустить, что в нашей программе таким образом обозначены все пути передачи аначений от результатов к аргументам, то принцип Б'сильно упрощается: для оператора Я занятыми являются все величины, пути которых «пересекают» этот оператор.
Не поленимся нарисовать эту картинку(рис. 1.1) для какого- нибудь из наших примеров, хотя бы пятого (ораву соображаем, что х для оператора ввода является результатом, а у для оператора вывода — аргументом). .Программа выглядит более громоздкой, но в то же время для наших целей необычайно ясной. Мы проложили по ней все пути. передачи аначений величии — от результатов к аргументам.
Давайте сразу их назовем информационными связями между аргументами и результатамн операторов. Все эти связи ориентированы «вдоль» по направлению выполнения программы. Анализ этих связей дает нам полное представление о том, как надо распределять память в программе. Действительно, подчеркнем мысленно каждый оператор горизонтальной линией, которая будет отмечать момент выполнения этого оператора. Назовем эту линию сечением программы. Тогда число информационных связей, пере- е ье. нАкопленне ФАктов линееные пРОГРАммы 23 секаемых сечением, показывает нам, сколько величин в настоящий момент «занято», т.
е. используются для хранения результатов, которые выработаны раньше, но потребуются позднее, а символы величин, сопоставленных концевым точкам зтих «маршрутов», указывают, какие конкретно величины используются. анана бещесаееннме хух3х«,хо,х16,хК; Рис. 1.1. Программа с провов«евиыми информациоввмми связями. Последнее наблюдение немедленно подсказывает нам систематическую процедуру переобозначения величин программы, дающую наименьшее количество обозначений. Чтобы подчеркнуть ее 24 Гл.
ь содвгжАтвльный АНАлиэ 3АдАчи. систематичность, мы намеренно выберем совсем другие обозначения: 11, 12 и т. д. Процедура экономии памяти в линейных программах« 1. Н а ч а л ь н ы й ш а г: берем первый оператор. Он содержит только результат, которому сопоставляется величина И. Имя этой же величины сопоставляется всем аргументам операторов, к которым ведут от этого результата информационные свяэи. 2. О ч е р е д н о й ш а г: берем очередной оператор Я. Пусть к этому времени уже использованы некоторые величины. Из этого набора отбрасываем занятые величины, т. е.
величины, информационные свяаи которых пересекаются сечением оператора Я. Если в наборе останутся величины, выбираем из них любую (например, с наименьшим номером) и сопоставляем ее результату оператора Я. Если все испольаованные величины «заняты», добавляем к ним еще одну, которую и сопоставляем результату. Имя величины„ сопоставленной результату оператора Я, сопоставляем всем аргументам операторов, к которым ведут от этого реаультата информационные связи. Очевидно, что если для каждого аргумента есть задающий его результат, то все величины программы получат новые имена; при этом их будет всего ровно столько, какова максимальная ширина сечений программы, т.
е. максимальное количество промежуточных значений величин, которые нужно хранить в какой-либо момент выполнения программы. Действительно, согласно процедуре мы добавляем к списку использованных величин новую только тогда, когда все величины заняты, а нам надо увеличить текущую ширину на единицу добавлением новой информационной связи. Применив эту процедуру к рис. 1.1, мы получим следующую программу: начало вещ 11, 82, »3, 14, 15; ввод (11); 12: = 11 х 11; 13:= г2 х 12; 13:= 13 х»З; 14:= 13хгЗ; 15:= 14х 14; 11:= И Х12; 11:= Н ~гЗ; 11:= 11х14; 11:= 11хг5; вывод (11) конец Только что полученная процедура является серьезным шагом вперед.
Мало того, у нас уже зреет убежденность, что она пол- а <.в. ПАкопление ФАктОВ. линейные пРОГРАммы 25 Костью решает вопрос об экономии памяти в линейных программах. Это побуждает нас продолжить ее анализ. Операторная схема. Возможно, кое-кто иа читателей уже обратил внимание на то, что после того как мы построили информационные свяаи программы, исходные имена величин, употребленных в ней, нам уже не нужны.
Мало того, они нам даже мешают, Рве. 1.2. Ии<уерт<ааяеииые связи делают имена величии неиуа<мыми. азагорая<иваяв те места, в которых мы должны согласно процедуре проставлять имена новых величин. Нам будет приятнее работать с программой беа величин — только с .кружками, отмечающими места аргументов и результатов операторов (рис. 1.2). гз гл. ь соднгжлтвльньпт лнхлиз злдлчн При взгляде на это графическое изображение программы нам начинает бросаться в глаза неуместность алголовской стилистики и прочей информации о программе, которая была неотьемлемой частью при составлении программы, но становится не столь существенной кри решении нашей специальной задачи об экономии памяти.
Мы уже распрощались со списком описаний величин, да и с самими величинами после того, как они сослужили свою службу в построении информационных связей. Что же нам нужно по существу? Нам нужно знать, что операторы образуют линейный порядок. Для каждого оператора нам нужно знать, сколько у него аргументов и результатов (оператор ввода, например, может иметь несколько результатов).
Нам совсем не важно, какую функцию выполняет оператор. Другими словами, нам достаточно знать не саму программу, а только ее схему, в которой были бы только обозначения операторов, а не нх содержание, был бы указан порядок их выполнения, были бы как-то отмечены их аргументы и результаты, притом так, чтобы было удобно изображать нх информационные связи и подписывать к ним имена величин. При всем прн этом мы уже оценили полезность графического представления такой, как ее естественно назвать, операторной схемы.
Оставляя читателя в неведении относительно множества картинок, перерисованных разными авторами в поисках наглядности, мы сразу предложим ему операторную схему нашей программы в уже общепринятом графическом оформлении (рнс. 1.3). Прямоугольниками изобра'иены операторы. Их обозначения ставятся внутри.
Жирные стрелки указывают на порядок выполнения операторов. Маленькие кружки на отросточках — аргументы и результаты. Отростки, идущие по ходу стрелок,— результат, а напротив — аргументы. Имена величии, сопоставленные аргументам и результатам, пишутся рядом с кружочками (рис. 1.3, а). Пунктирные стрелки — информационные связи. Чтобы не загромождать чертежи (рис. 1.3, б), там, где зто удобно, пунктирные стрелки, идущие от одного результата, сливаются в одну связку.
Такое графическое сокращение даже удобно по существу. если подсчитывать ширину сечения, нужно все стрелки, идущие от одного результата, считать за одну, т. е. как раз считатьсвязками. На этом чертеже информационные связи нарисованы с «вывертами» вЂ” не по кратчайшему расстоянию,— для того, чтобы более четко показать ширину информационных связей.
Графическое представление схемы программы и ее информационных связей делает гораздо более понятным эффект перестановки операторов программы в примере 7 (рис. 1.3, в): сократив маршруты передачи значений от результатов к аргументам, мы разгрузили информационные связи и сократили их ширину до двух, что, кстати, в отличие от программы примера 7, видно на етой схеме с очевидностью. и 1.2. НАКОПЛЕНИЕ ФАКТОВ ЛИНЕЙНЫЕ ПРОГРАММЫ 27 пт гх .24 .24 . 24 Ю 24 пд ю8 вй дй вЮ Е ю47 Я д ЛЮ Е6 У Рис. 1.3.
Операторные схемы. и] Пример 5. 6) Информационные свявя примеров 5 и 6. в) Ияфорыациоиныв свяви примеров 7 и 8. Г 1 1 Г" Г 1 1 ! ГА- 1 ! ! и-т-Ч- 1 1 р гЗ 1 ~~-1-Г ! 1 ' Е гП -1 — !. 1 ГЕ Е Г ! гт т, ! 1 ! 1 11! 1 г 1 1 1 н 1 ! ! ! I г ! 1 Я ! У Г-! —— 1 р г П1 1 ! ! р и г+' о ГФ 1 н 1 1 л. 21 1 т 1 1 Г 2 28 ГЛ. Ь СОДЕРЖАТЕЛЬНЫЙ АНАЛИЗ ЗАДАЧИ Связки. Ширина сечений. Похоже, что мы ух<е исчерпали все полезные факты, которые нам могут дать линейные программы. Главными нашими достижениями являются открытие важности анализа информационных связей программы, а такяге извлечение из программы тех и только тех ее характеристик, которые нам помогают в решении аадачи экономии памяти и которые изображаются в виде ее операторной схемы.
После того как мы уже несколько освоились с этой находкой, давайте разберем подробнее, что такое информационная связь, как мы ее находим по заданной программе и как используем для распределения памяти. Мы прокладываем связь от результата оператора Я к аргументу оператора Т, если Я имеет своим результатом некоторую величину х, Т имеет х своим аргументом, Т выполняется позже Я, т. е. от У к Т ведет цепочка операторов, и, наконец, в этой цепочке ни один из операторов не имеет х своим результатом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
