AOP_Tom1 (1021736), страница 172
Текст из файла (страница 172)
Нужно выбрать такое !Ч и такое отношение разделения времени, чтобы операции (а)-(с() гарантированно завершались до того, как !Ч узлов будут извлечены иэ списка АЧА11, даже если основная программа выполняется достаточно быстро. При этом на этапе (Ь) необходимо убедиться в том, что маркированы все узлы, "доступные для данной программы", по мере ее выполнения, остальные подробности здесь опускаются. Если в созданном на этапе (с) списке содержится менее К узлов, то в конце концов может потребоваться прекратить работу приложения из-за того, что в памяти будет исчерпано все свободное пространство.
Более подробные сведения по этой теме приводятся в работах Сиу 1.. ЗСее!е Юг., САСМ 18 (1975), 495 — 508; Р. 1Час)!ег, САСМ 19 (1976), 491-500; Е. ЪЧ. Р!!)сэСга, Ь, ! апсрогс, А. 1. Магсш, С. Я. ЯсЬо1сеп, апс1 Е. Г. М. Все!(епэ, САСМ 21 (1978), 966-975; Н. С. Ва!сег, Зг,, САСАХ 21 (1978), 280-294. РАЗДЕЛ 2.4 1. В прямом порядке.
2. Оно прямо пропорционально количеству создаваемых элементов таблицы данных. 3. Заменить операции шага А5 такими действиями. А5'. [Удаление верхнего уровня.] Удалить верхний элемент стека; и если номер нового уровня на вершине стека равен > Ь, то пусть (11, Р1) — новый элемент на вершине стека. Повторить этот шаг. В противном глучае установить 318(Р1) с — О. Тогда пусть (11. Р1) является новым элементом на вершине стека. 4. (Решение Дзвида С. Вайса (РачЫ 8. ЧЧ!эе).) Правило (с) нарушается тогда н только тогда, когда существует элемент данных, полная квалификация Аэ Оу... ОГ А„которого в языке СОВОЬ также является ссылкой на некоторый элемент данных. Так как и родитель Ас ОГ... ОГ А„должен удовлетворять правилу (с), можно предположить, что этот другой элемент данных является наследником некоторого родителя.
Значит, алгоритм А следует расширить таким образом, чтобы при добавлении в таблицу данных каждого нового элемента данных выполнялась проверка, является ли его родитель предком любого другого элемента данных с таким же именем или есть ли в стеке родитель любого другого злеиента с таким же именем. (Когда родитель равен Л, он является предком всех других элементов и всегда располагается в стеке.) С другой стороны, если оставить алгоритм А в прежнем состоянии, программист при выполнении СОВОЬ-программы получит сообщение об ошибке со стороны алгоритма В при попытке использования недопустимого элемента. И тшсько при выполнении команды МОЧЕ СОННЕБРОМ01МС элементы данных иогут применяться без вывода сообщения об ошибке. б.
Следует выполнить такие изменения. На шаге команду заменить командой В1 Р +- 1-1МК(Ро) Р:— 1.1МК(1МГО(Т) ) В2 lс ь-0 К ь- Т ВЯ й(п И.1МК(К) Ф Л В4 А +- /с + 1 К +- НЬ1МК(К) Вб МАИЕ(5) = Рь МАМЕ(5) = 1МГО(К) 6. Простое изменение алгоритиа В позволяет выполнять поиск только полных ссылок (если А = и и РАНЕМТ(3) Р Л на шаге ВЗ или если МАМЕ(5) Р' Рг на шаге Вб, то в таком случае следует установить Р с — РНЕЧ(Р) и перейти к шагу В2).
Основная идея здесь заключается в том, чтобы сначала выполнить иодифицироваиную версию алгоритма В, а затем, если ссылка Ц осе еще равна Л, — его немодифицированную версию. Т. МОЧЕ НОМТН ОР ОХТЕ ОГ БАСНЯ ТО ИОМТН ОГ ОАТЕ ОР РОНСНАБЕЯ. ИОЧЕ ОАТ ОГ ОАТЕ ОР ЯАЬЕБ ТО ОАТ ОГ ВАТЕ ОР РСНСНАБЕЯ. ИОЧЕ ТЕАК ОГ ОАТЕ ОГ БАСНЯ ТО ТЕАН ОР ОАТЕ ОР РОНСНАЯЕБ. МОЧЕ 1ТЕИ ОР ТНАМЯАСТТОМ ОР БАСНЯ ТО 1ТЕМ ОГ ТНАМЯАСТ10М ОГ РОНСНАЯЕБ. МОЧЕ ЦОАМТТТТ ОГ ТНАМЯАСТ1ОМ ОГ БАСНЯ ТО ЦОАМТ1ТТ ОГ ТНАИБАСТ103 ОГ РОНСНАБЕЯ. ИОЧЕ РН1СЕ ОГ ТНАМБАСТ1ОМ ОР БАСНЯ ТО РН1СЕ ОГ ТНАМ5АСТ10М ОГ РОКСНАБЕБ.
МОЧЕ ТАХ ОГ ТНАМБАСТТОМ ОГ ЯАЬЕЯ ТО ТАХ ОР ТНАМЯАСТ10М ОГ РОНСНАЯЕЯ. 8. Тогда и только тогда, когда и или )) является простейшим элементом. (Может быть, следует отметить, что автору не удалось должныи образом обработать этот случай в первом черновом варианте алгоритма С, что существенно усложнило этот алгоритм.) 9. Если ни о, ни )5 не является простейшим элементом, то коианда ИОЧЕ СОННЕЯРОМ01МС о ТО 1) эквивалентна набору команд ХОЧЕ СОННЕЯРОИ01МС .4 ОР о ТО А ОГ (), выполненному над всеми именами А, общими для групп о и )5. (Этот способ опредш ленин элегантнее, чем более традиционное и тяжеловесное определение команды ИОЧЕ СОККЕЯРОМ01МС, которое предлагается в тексте.) Можно убедиться, что алгоритм С удовлетворяет такому определению, доказав по индукции, что после выполнении шагов С2 — С5 в конце концов получится Р = РО и Ц = ЦО.
Далее доказательство проводится точно так, как оио выполнялось много раз прежде, в "индукции по дереву" (см, например, доказательство алгоритма 2.3.1Т) . 10. (а) Установить 51 с- 11МК(РА). Затем повторно ни разу ие устанавливать или устанавливать 51 с- РНЕЧ(51) до тех пор, пока либо 51 = Л (МАМЕ(5) Р Рг), либо 51 = 3 (ИАИЕ(5) = Рг). (Ь) Установить Р1 с — Р, а затем ии разу не устанавливать или устанавливать Р1 с- РНЕЧ(Р1) до тех пор, пока не выполнится условие РНЕЧ(Р1) = Л. Выполнить аналогичную операцию для переменных Ц1 и Ц, затем проверить Р1 = Ц1.
Иначе, если позиции таблицы данных упорядочены так, что РНЕЧ(Р) < Р для всех Р, более быструю проверку, очевидно, можно выполнить следующим образом: выяснить, что Р > Ц, или, наоборот, пройти по связям РНЕЧ большего из них и обнаружить, встречается ли меньший из них. 11. Незначительного повышения скорости выполнения шага С4 можно достичь за счет добавления нового полн связи Б1В1(Р) ш СНТЬО(РАНЕМТ(Р) ). Увеличение скорости будет более существенным, если модифицировать связи СНТСО и БТВ таким образом, чтобы МАМЕ(Б1В(Р) ) > МАМЕ(Р) . Это позволит значительно ускорить поиск на шаге СЗ, поскольку для этого потребуется выполнить только один проход по каждому семейству для поиска подобных членов Следовательно, такое изменение позволяет исключить единственную операцию поиска в алгоритме С. Алгоритмы А и С можно легко модифицировать с предложенной интерпретацией, а читателю будет полезно выполнить ее в качестве интересного упражнения.
(Однако, если рассмотреть относительную частоту команд МОЧЕ СОННЕБРОМО1МО и обычный размер семейных групп, полученное в результате повышение скорости будет не таким уж значительным после трансляции реальных СОВОЬ-программ.) 12. Шаги В1-ВЗ остаются прежними, а другие шаги будут выглядеть так В4. Установить М ь- А + 1, Н т- 51МК(Рь) . ВЯ. Если Н = Л, то соответствия нет; установить Р ь- РНЕЧ(Р) и перейти к шагу В2. Если Н < Я < БСОРЕ(Н), установить Я +- Н и перейти к шагу ВЗ.
В противном случае установить Н т- РНЕЧ(Н) и повторить шаг В5. $ Этот алгоритм не адаптирован для соглашений, принятых для языка Рь/1 в упр. 6. 13, Используйте тот же алгоритм, но без операций установки связей МАМЕ, РАНЕМТ, СНХСО и Я1В. При каждом удалении верхнего элемента стека на шше А5 следует устанавливать БСОРЕ(Р1) ь- Ц вЂ” 1. После исчерпания входного потока на шаге А2 следует просто установить 1 ь- О и продолжить выполнение алгоритма. Затеи необходимо прекратить выполнение алгоритма, если 1. = О на шаге А7.
14. Шаги приведенного ниже алгоритма со вспомогательным стеком пронумерованы так же, как шаги алгоритма С, приведенного в данном разделе, для упрощения их сравнительного анализа. С1. Установить Р г — РО, Ц +- ЦО и опустошить стек. С2. Если ЯСОРЕ(Р) = Р или БСОРЕ(Ц) = Ц, вывести (Р,Ц) как одну из искомых пар и перейти к шагу С5. В противном случае поместить (Р, Ц) в стек и установить Р +- Р + 1, Ц + — Ц -~- 1. СЗ. Определить, указывают ли Р и Ц на элементы с тем же именем (см. упр 10, (Ь)).
Если указывают, то перейти к шагу С2. Если не указывают, то поместить (Р1, Ц1) в верхнюю часть стека; если БСОРЕ(Ц) < ЯСОРЕ(Ц1), то установить Ц г — БСОРЕ(Ц) + 1 и повторить шаг СЗ С4. Поместить (Р1, ц1) в верхнюю часть стека. Если БСОРЕ(Р) < БСОРЕ(Р1), то устанш вить р+- БСОРЕ(Р)+1, Ц + — Ц1+1 и перейти к шагу СЗ. Если БСОРЕ(Р) = ЯСОРЕ(Р1), то установить Р г — Р1, Ц +- Ц1 и удалить иерхний элемент стека, Сб.
Если стек пуст, прекратить выполнение алгоритма. В противном случае перейти к шагу С4. Б РАЗДЕЛ 2.5 1. В столь благоприятных ситуациях можно воспользоваться стековыми операциями следующим образом. Пусть область пула памяти имеет адреса от О до М вЂ” 1 и пусть АЧА1). указывает на нижний свободный адрес. При выделения М слов, если АЧАП. + М > М, сообщается о невозможности выделения необходимого количества памяти, в противном случае устанавливается АЧАП. г — АЧАП. + М, Для освобождения этих М слов просто устанавливается АЧА11 +- АЧА15 — М. Аналогично для метода "первым выделен — первым освобожден" используются операции с циклической очередью. 2. Количество памяти, необходимой для хранения элемента длиной 1, составляет 511/(А — Ь)~1, среднее значение которого равно ЬЕ/(Ь вЂ” Ь) + (1 — а) А, где о предполагается равным 1/2, не зависящим от А. Это выражение минимально (для действительных значений Ь) при А = Ь+ л/255.
Поэтому выбор )г равным ближайшему (сверху или снизу) к этой величине целому значению дает наименьшее значение )гь/(Ь вЂ” Ь) + -'Ь. Например, при Ь = 1 и 5 = 10 следует принять А 1+ ь/20 0= 5 или 6; оба значения одинаково хороши. Более детально эта задача рассматривается в дАСМ 12 (1965), 53 — 70. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
