1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 6
Текст из файла (страница 6)
Для построения информационных связей и вообще, для решения задачи экономн1г памяти, нам достаточно иметь операторную схему программы, в которой указаны символы операторов, их аргументы, результаты и сопоставленные им имена величин, а также порядок выполнения операторов. После построения всех информационных связей программы исходное распределение памяти нам уже не нужно. Мало того, по совокупности информационных связей мы можем построить любое другое распределение памяти в данной программе, в том числе и самое экономное по числу использованных величин. Информационные связи в операторной схеме группируются в связки. В одну связку входят все информационные связи, выходящие из некоторого результата.
Для правильного распределения памяти нужно, чтобы всем аргументам и результату, входящим в связку, была бы сопоставлена одна и та >ке величина. Самое неэкономное распределение памяти получается, когда каждому результату, или, что то же самое, каждой связке сопоставляется своя величина. Экономия памяти достигается тогда, когда нескольким связкам сопоставляется одна и та л1е величина. Однако чтобы не нарушить информациош1ые связи, нельзя сопоставлять одну и ту же величину конкурирующим информационным связям.
В линейной программе конкурирующими являются те и только те связки, которые одновременно пересекаются каким-либо сечением ее операторной схемы. Для линейной программы есть простой алгоритм нахождения экономного распределения памяти. Число. используемых величин при этом оказывается равным ширине сечений, т. е. максимальному числу связок, рассекаемых сечениями. Эти выводы мы теперь примем в качестве рабочих гипотез, которые будем проверять на более разнообразных примерах в поисках новых фактов. Очевидно, что прежде всего нам надо уело'книть структуру программ.
$ ЬЗ. НАКОПЛЕНИЕ ФАКТОВ ПРОГРАММЫ ОБЩЕГО ВИДА 29 ф 1.3. Накопление фактов. Программы общего вида Программа с условиями. П р и м е р 9. Решить квадратное уравнение ахз + Ьх + с = О для общего случая. Комплексное решение представить в виде значений модуля и аргумента комплексно сопряженных корней. Представив общую формулу решения — Ь + $'гьа — 4ас х!,2 = 2а Ь гг( Ьс — 4ас ( в виде р= — — и о =- 2а 2а , мы затем в зависимости от знака дискриминанта Ь' — 4ас найдем для действительного случая прион = 1, кор1 = р + д и кор2 = р — д, а для комплексе ного ' — прион = — 1, кор1 = )г рз+д'и кор2 =агасси ~ В Результате введя для зкономии вычислений еще несколько промел'уточных величин, но в то же время пе стремясь расписать все формулы до последней операции, получим программу: начало вещ а, Ь, с, 21, 22, дискр, р, 4!, кор1, кор2: цел прион; ввод (а, Ь, с); 21:= 2ха; 22:= 2хс; дискр:= Ь ('2 — Н хс2; р:= — ЬМ; ос= здгЬ(ада(дискр))121; если дискр < 0 то начало П:= р1.2+ д12; кор1: = здг!(!1); кор2: = агсзсп (!р'кор1) конец иначе начало кор1:= р + д; кор2:= р — д; конец; призн:= зсвп (дискр); вывод (призн, кор1, кор2) конец Маршрут.
Построим теперь Для атой программы ее операторную схему. Она уже не будет линейной, потому что в ней содержатся взаимноисключающие участки вычислений (случай отрицательного и неотрицательного дискриминанта). Для удобства ' $ Ьз, НАКОПЛЕНИГ ФАКТОВ. ПРОГРАММЫ ОВШЕГО ВИДА 3$ дальнейшего аналива обозначим каждый из операторов именем величины, сопоставленной его результату, сделав очевидные исключения для операторов условия и вывода. На схеме (рис. 1.4) проложим информационные связи, используя то же правило: свяаь прокладывается от результата оператора Я к аргументу оператора Т, если им сопоставлена одна и та же величина х и существует хотя бы один путь по схеме от Я к Т, вдоль которого ни один из операторов, кроме Я, не вырабатывает величину х.
У нас уяоэ промелькнуло образное сравнение этого пути с маршрутом доставки аначения величины х от оператора Я к оператору Т. Сейчас нам, пожалуй, будет самое подходящее время закрепить этот образ в виде термина. Одно иа новых явлений, которые мы обнаружили на этой схеме, это то, что доставка значения от результата к аргументу, т.
е. реалиаацня проложенной информационной связи, может происходить более чем по одному маршруту: значение дис доставляется к оператору прион либо по маршруту (дис, р, д„ Г-,11', кор1, яор2, призн), либо (дис, р, д, <, корМ', кор2', нрилн). Второе наблюдение касается связок информационных связей: до сих пор каждая связка была как бы пучком стрелок, идущих от одного реаультата к нескольким использующим его аргументам. Сейчас л;е (рис.
1.5) нх конфигурация усложнилась: в случае 7 / / а/лад р à — Ч ау 'аг РИС. 1.5. НОВЫЕ ВиДЫ СВЯЗОК ДЛЯ кави И АОР2. связки ноо2 информационные связи группируются у аргумента, а в связке нор1 группировка произошла и у аргумента, и у результата. Это заставляет нас сделать заметку на будущее (правда очень скорое): при выборе имени величины для обозначения результата это имя нужно расставить не только на аргумент (или аргументах), двигаясь по стрелкаи, ио и потом перенести имя с этого аргумента на другой результат, навстречу стрелке соответствующей информационной связи.
32 ГЛ. С СОДКРЖАТЕЛЪНЫН АНАЛИЗ ЗАДАЧИ Следующее, что мы хотим сделать,— это провести сечения последовательности выполненных операторов, чтобы определить конкурирующие информационные связи и число величин в экономном распределении памяти. При проведении сечений мы опять- таки сталкиваемся с новыми фактами. У нас по-прежнему есть, как бы сказать, доминирующее направление вычислений, аадаваемое стрелками между операторами, при этом распадающееся на некотором участке на две ветви, которые потом снова сходятся. Мы уже понимаем, что на нашем примере изображен простейший случай и что, желая выжать из этого конкретного примера все полезное, мы должны стараться сформулировать наши возможные новые правила в наиболее общей форме.
Само понятие сечения не зависит от сложности схемы. Мы всегда рассекаем только одну стрелку перехода от одного оператора к другому. Вопрос в том, какие информационные связи мы рассекаем этим сечением. Раньше ответ был прост: все те, которые начинаются выше и кончаются ниже данного сечения.
Простота его для линейной ирограммы была в том, что каждый оператор программы оказывался либо ниже, либо выше сечения. Здесь это уже не так: выше или ниже оператор иор1 по отношению к оператору иор2 — этот вопрос не имеет ни смысла, ни ответа. Вспомним, однако, как мы использовали сечение: мы каждой пересекаемой информационной свяаке сопоставляли величину, хранившую выработанное значение и говорили себе: вот эти величины заняты в момент выпоянения рассекаемого оператора е), поэтому его результат нельзя присвоить нн одной из этих аанятых величин, н информационная связь, начинаемая этим результатом, является конкурентной со всеми другими рассекаемыми информационнымн связями. Тогда мы можем сказать так: сечение некоторого оператора Я рассекает по определению те и только те информационные связи, маршруты которых содержат Я, или: информационная связь, начннаемая результатом некоторого оператора Я, конкурентна с теми и только с теми информационными связями, маршруты которых содержат Я.
Эта формулировка, хотя и выглядит более сложной, зато более непосредственно вырангает суть дела (принцип сохранения информационных связей), а главное,— уже не аависит от конкретной сложности схемы: если мы знаем информационные связи и реализующие их маршруты, мы можем построить все сечения, ибо вопрос о принадлежности того или иного оператора тому или иному маршруту решается однозначно. Подробная процедура зкономии.
На рис. 1.6 изображены все 14 сечений схемы примера 9. Нам с ними еще придется поработать, е] мы лла краткости употребляем еельиое выражение, тан пан рассекаем фактически ие оператор, а выходящую ил лего стрелку перехода. я 1.3. ИАкОпление ФАктОВ. пРОГРА31ааы ОВщеГО ВидА ЗЕ Рис. 1,6. Распредалеыие памяти для прямера 9. ГЛ,1$ СОДЕРЖАТЕЛЬНЫЙ АНАЛИЗ зАДАчИ поэтому они занумерованы. Справа указана ширина как<доге сечения, т. е.
количество взаимно конкурирующих информационных связей. Максимахьная ширина равна четырем. Приступим к распределению памяти согласно процедуре, отработанной нами'для линейных программ. Нам имеет смысл один раз выполнить ее;во всех деталях. Читателю рекомендуется перерисовать рис.
1.6 без имен величин и проставлять их на рисунке по мере продвижения по схеме. С е ч е'н и е 1. Три реаультата. Обоаначаем их а, Ь и си переносим имена на аргументы по направлению информационных свяаей. С е ч е н и е 2. Новый реаультат, Ь и с заняты, а свободно Обозначаем им результат и соответствующие аргументы. Се че н и е 3. Новый результат, а и Ь заняты, с свободно Обозначаем им реаультат и (соответствующие) аргументы. С е ч е н и е 4. Новый результат, а и Ь заняты, с свободно Обозначаем им результат и аргументы. С е ч е н и е 5. Новый результат, а и с заняты, Ь свободно Занимаем его.
Се че н ив 6. Новый реаультат, Ь и с заняты, а свободно Занимаем его. Се чек не 7. Результатов нет. Се че н и е 8. Новый результат, а и с заняты, Ь свободно Занимаем его. Се ч е н не 9. Новый результат, а и с заняты, Ь свободно Занимаем его. Однако, когда мы перенесем Ь на аргументы операторов кор2 и выз, мы увидим, что эта же величина должна быть соотнесена результату оператора кор1'.
Однако этого делать нельзя, так как в сечении 12 этот результат конкурирует, в частности. с информационной связью от р к кор2', которой в свое время уник была сопоставлена величина Ь. Нам не остается ничего другого, как взять для рассматриваемой свяаки кор1 новую величину 3. С е ч е н и е 10.
Новый результат, с и д заняты, а и Ь свободны. Берем а в качестве величины для результата и опять обнаруживаем, что его надо перенести и на результат кор2'. Анализ 13-гь сечения, однако, позволяет это сделать. С е ч е н и е 11. Результатов нет. С е ч е н и я 12 и 13. Величины реаультатам уже сопоставлены С е ч е н и е 14. Новый результат, а и 3 ааняты, Ь и с свободны Занимаем Ь. Проанализируем итог работы. В первом приближении процедура экономии памяти сработала как нужно: максимальная ширина схемы (12-е сечение) равна четырем, именно столько величин мы испольаовали. Анализ сечений по-прежнему давал нам сведения о занятых величинах в момент выполнения рассматриваемого оператора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
