AOP_Tom1 (1021736), страница 171
Текст из файла (страница 171)
Выполнить переход, если Ц = Л. и — Ь и — Ьз и — Ьт НАВК(Ц) с — 1. Выполнить переход, если узел ИОВЕ(Ц) уже маркирован. 28 28 80 81 82 88 84 85 Эб 87 ЬОА 0,3(АТОН) ЗАИК Еб БТ2 0,1(ВПИК) ЕИТ2 0,1 ЕИТ1 0.3 ЬОЗ 0,1(АЬТИК) 132 ЕБ ЬОА 0,3 БТХ 0,3(МАЯК) )АИР ЕБ Сг+ аз 12+ аг ст и — 1 и — 1 Выполнить переход, если АТОН(Ц) = 1. В1.1ИК(Р) с- Т. Т с- Р.
Р с-Ц. Е4. Вниз по связям АПИК. Ц+- А1.1ИК(Р). Выполнить переход, если Ц = Л. Е4А Е4 и и — Ьг и — Ьг и — Ьг МАЯК(Ц) с- 1. Выполнить переход, если узел ИОВЕ(Ц) уже маркирован. ЫА 0,3(АТОН) ЗАИК ЕБ БТХ 0,1(АТОН) БТ2 0,1(АПИК) ЛСР Е4А 88 ЭУ 40 41 42 Сг ба~ с~+а~ с сг Выполнить переход, если АТОМ(Ц) = 1.
АТОИ(Р) +- 1. А1.1ИК(Р) с- Т. Т е- Р, Р с- Ц, переход к шагу Е4. ! По закону Кирхгофа Сг+Сз+1 = и. Общее время выполнения равно (34ил-4(г+За — 56 — 8)и, где и — количество маркированных узлов, не являющихся атомами, а — количество марки- рованных атомов, Ь вЂ” количество связей Л, которые встречаются в маркированных узлах, не являющихся атомами, С~ — число переходов вниз по связяы А11ИК (О < Сг < и). 01 02 08 04 05 05 07 08 00 10 11 12 1Э 14 15 1б 17 18 10 20 21 22 28 24 25 Яб 27 НАВК АТОМ АПИК ВПИК Е1 Е2 ЕЗ Еб 1Н ЕБ ЕЦО 0:0 ЕЦО 1:1 ЕЦО 2:3 ЕЦО 4:Б ХО1 РО ЕИТ2 0 ЕИТХ -1 БТХ 0,1(НАКК) ЬОА 0,1(АТОН) 1А2 Е4 122 РОМЕ ЕИТЗ 0,2 ЬОА 0,3(АТОН) ЗАИ2 1Р 602 0,3(ВЫИК) БТ1 0,3(ВПИК) ЕИТ1 0,3 ЭНР Еб БТ2 0,2(АТОН) 602 0,3(АПИК) БТ1 0,3(А1.1ИК) ЕИТ1 0,3 103 0,1(В1.1ИК) 132 Еб ЬОА 0,3 БТХ 0,3(НАВК) ЗАИР Еб 5.
(Приведенный ниже алгоритм является самым быстрым из известных до сих пор алгоритмов маркировки для одноуровневой памяти.) Б1. Установить НАЙК(РО) ь- 1, Если АТОН(РО) = 1, то выполнение алгоритма прекращается; в противном случае установить Я ь- О, Й е- РО, Т ь- й. Я2. Установить Р +- Б11МК(Й). Если Р = й или НАЙК(Р) = 1, перейти к шагу ЯЗ. В противном случае установить НАЙК(Р) +- 1. Теперь, если АТОН(Р) = 1, перейти к шагу ЯЗ; в противном случае, если Б < М, установить Я ь- Я+ 1, ЯТАСК[Я) ь- Р и перейти к шагу ЯЗ; в противном случае перейти к шагу Я5.
ЯЗ. Установить Р ь- АЕ1МК(Й). Если Р = Л или МАЙК(Р) = 1, то перейти к шагу Я4. В противном случае установить НАЙК(Р) <- 1. Теперь, если АТОН(Р) = 1,перейти к шагу Б4;в противном случае установить Й < — Р и вернуться к шагу Б2. Б4. Если Я = О, то прекратить выполнение алгоритма; в противном случае установить Й <- ЯТАСК[Я), Я < — 3 — 1 и перейти к шагу Я2. Яб.
Установить Ц <- АЕ1МК(Р). Егли Ц = й или НАЙК(Ц) = 1, то перейти к шагу Яб. В противном случае установить НАЙК(Ц) <- 1. Теперь, если АТОМ(Ц) = 1,перейти к шагу Яб; в противном случае установить АТОН(Р) +- 1, АПЕК(Р) ь- Т, Т ь — Р, Р +- Ц и перейти к шагу Я5. Яб. Установить Ц г- Б1.1МК(Р). Если Ц = Л или МАКК(Ц) = 1, то перейти к шагу Я7; в противном случае установить НАЙК(Ц) ь- 1. Теперь,ели АТОН(Ц) = 1, перейти к шаху Б7; в противном случае установить БЕ1МК(Р) ь- Т, Т +- Р, Р +- Ц и перейти к шагу Б5. БТ. Если Т = Л, то перейтн к шагу БЗ. В противном случае установить Ц <- Т.
Если АТОМ(Ц) = 1, то установить АТОМ(Ц) Ь- О, Т г- А1.1МК(Ц), А1.1МК(Ц) ь- Р, Р з- Ц и вернуться к шагу Бб. Если АТОН(Ц) = О, то установить Т +- Б1.1МК(Ц), Б1.1МК(Ц) +- Р, Р +- Ц и вернуться к шагу Я7. $ [Сас САСА[ 10 (1957), 501 — 50б.] 8. Он включен и связи с выполнением второй фазы сборки мусора (или начальной фазы, если все маркировочные биты инициализируются в зто время нулями). 7. Следует удалить шаги Е2 и ЕЗ. а также команду "АТОН(Р) ь- 1" на шаге Е4.
Установить НАЙК(Р) +- 1 на шаге Е5 и использовать команду "НАЙК(Ц) = 0", "НАЙК(Ц) = 1" на шаге Еб вместо команд "АТОМ(Ц) = 1", "АТОН(Ц) = 0" соответственно. Основная идея здесь заключается в установке маркировочного бита НАЙК только после маркирования левого поддерева. Этот алгоритм вполне пригоден, даже если дерево имеет перекрывающиеся (совместно используемые) поддеревья, но его нельзя применить для всех рекурсивных структур Списка, в которых узел МООЕ(А11МК(Ц)) предшествует узлу МООЕ(Ц). (Обратите внимание, что связь АЕ1МК маркированного узла никогда пе меняется.) 3. Решение 1.
Оно аналогично алгоритму Е, но проще. Е1. Установить Т ь- й, Р г — РО. Е2. Установить МАЕК(Р) <- 1 и Р г- Р+ Я12Е(Р) . ЕЗ. Если НАЙК(Р) = 1, перейти к шагу Г5. Е4. Установить Ц < — 1.1МК(Р). Если Ц Зе Л и НАЙК(Ц) = О, то установить 1.1МК(Р) +- Т, Т +- Р, Р <- Ц и перейти к шагу Г2. В противном случае установить Р <- Р— 1 и вернуться к шагу РЗ.
Еб. Если Т = й, прекратить выполнение алгоритма. В противном случае установить Ц+- Т, Т Ф- ПНК(Ц), ЫМК(Ц) ь- Р, Р ь- Ц вЂ” 1 н вернуться к шагу ГЗ. $ Аналогичный алгоритм, который иногда позволяет сократить связанные с выделением памяти накладные расходы и избежать размещения всех указателей внутри узлов, предложил Ларс-Эрик Торелли [Ьагя-Еггй ТЬоге!1(), см. В1Т 12 (1972), 555-568. Решение 3, Оно аналогично алгоритму )). В этом решении предполагается, что поле 312Е достаточно велико и в нем можно разместить адрес связи. Такое допущение, вероятно, не оправдано в данной постановке задачи, но оно позволяет получить несколько более быстрый алгоритм, чем алгоритм из первого решения.
С1. Установить Т <- Л, ИАНК(РО) е- 1. Р е- РО .~- 312Е(РО). С2. Если ИАНК(Р) = 1, перейти к шагу С5, СЗ. Установить Ц +- 1.1ИК(Р), Р г- Р— 1. С4. Если Ц ф Л и ИАНК(Ц) = О, то установить ИАНК(Ц) +- 1, 3 г- 312Е(Ц), 312ЕИ)) +- Т, Т с- Ц + 3. Вернуться к шагу С2. С5. Если Т = Л, прекратить выполнение алгоритма. В противном случае установить Р с- Т и найти первое значение среди Ц = Р, Р— 1, Р— 2,..., для которого ИАНК(Ц) = 1; установить Т < — 312Е(Ц) и 312Е(Ц) < — Р— Ц.
Вернуться к шагу С2. $ 9. Н1. Установить Ь ~- О, К с — И+ 1, МАЕК(О) г- 1, ИАНК(И+ 1) с — О. Н2. Увеличить Ь на единипу и, если ИАНК(Ь) = 1, повторить этот шаг. НЗ. Уменьшить К на единицу и, если ИАНК(К) = О, повторить этот шаг. Н4. Ешги Ь > К, то перейти к шагу Нб; в противном случае установить МОРЕЙ) г— ИООЕ(К), АПИК(К) +- Ь, ИАНК(К) <- О и вернуться к шагу Н2. Н5.
Для 1. = 1, 2, ..., К выполнить такие действия, Установить ИАНК Й) с- О. Если АТОИ(Ь) = О и АПИК(Ь) > К, то установить АЬ1ИК(Ь) +- АПИК(АПИК(Ь)). Если АТОИ(Ь) = 0 и ЕПИК(Ь) > К, то установить ВЬ1ИК(Ь) +- АЬ1ИК(ВПИК(Ы). $ [См. также упр. 2.5-33.) 10. Е1. [Инициализация,] Установить Г ь- РО, Н ~ АГАП., ИООЕ(Н) г- ИООЕ(Г), НЕГ(Р) Г- Н. (Здесь Г и Н вЂ” указатели очереди в полях НЕГ всех встретившихся узлов-заголовков.) Е2.[Начало нового Списка.] Установить Р е- Г, Ц с- НЕГ(Р).
ЕЗ. [Продвижение вправо.) Установить Р е- НЬ1ИК(Р). Если Р = Л, то перейти к шагу 26. 24.[Копирование одного узла.) Установить 61 ~ АЧА1Ь, НЬ1ИК(Ц) г — Ц1, Ц < — Ц1, ИООЕ(Ц) г- ИООЕ(Р). Еб.[Преобразование связи подСписка.] Если Т(Р) = 1, то установить Р1 < — НЕР(Р) и, если НЕГ(Р1) = Л, установить НЕР(Н) +- Р1, Н ч- АЧА11., НЕГ(Р1) с в Н, ИООЕИА) +- ИООЕ(Р1), НЕГ(Ц) ь- Н. Если Т(Р) = 1 и НЕГ(Р1) ф Л, то установить НЕГ(Ц) ГНЕР(Р1). Перейти к шагу 23. Е6. [Переход к следующему списку.] Установить 31.1ИК(Ц) <- Л. Если НЕГ(Г) ~ Н, то установить Г с- НЕГ(НЕГ(Р)) и вернуться к шагу 22. В противном случае установить НЕГ ОТ) +- Л, Р с- РО.
ЕТ. [Окончательная за.гистка.) Установить Ц +- НЕГ(Р). Если Ц ф Л, то установить НЕГ(Р) +- Л и Р <- Ц и повторить шаг 27. $ Конечно, такое применение полей НЕГ не позволяет испольэовать метод сборки мусора с помощью алгоритма П; более того, алгоритм 1) непригоден здесь еще и потому, что во время копирования не сохраняется структура Списков. Несколько элегантных алгоритмов копирования и перемещения Списков основаны на гораздо более слабых предположениях о представлении Списка; см. Э. %.
С!аг)с, САСМ 19 (1976), 352-354; 1. М. ВоЬэоп, САСМ 20 (1977), 431-433. 11. Выполним зто упражнение вручную с помощью карандаша н бумаги, хотя можно было бы привести и более формальное решение, Сначала зададим уникальное имя (например, с помощью заглавнмх букв) для каждого Списка рассматриваемого множества. В данном примере получим А = (а: С,Ь, а: Р), Р = (Ь: Р), В = (а; Р,Ь,а: Е), С = (Ь;С), С = (а: С), Р = (а:Р), Е = (Ь:С). Теперь построим список из пар имен Списков, эквивалентность которых необходимо доказать. Последовательно будем добавлять пары в этот список до тех пор, пока не получим противоречие из-за наличия противоречивых пар на первом уровне (тогда исходные Списки не эквивалентны), или до тех пор, пока нз списка пар не будут следовать никакие другие пары (тогда исходные Списки не эквивалентны). В данном примере список пар в исходном состоянии содержит только заданную пару, АВ; затем в него будут добавлены пары СГ, ЕР (при сравнении А и В), РС (гледует из СР), после чего получится непротиворечивое множество.
Для доказательства корректности этого метода обратите внимание на то, что (с) при получении ответа "не эквивалентны" заданные Списки не эквивалентны; (й) если заданные Списки не эквивалентны, то будет получен ответ "не эквивалентны'": (ш) работа алгоритма всегда завершается. 12, Если список АЧА11 содержит )Ч узлов, где !Ч вЂ” константа, выбор которой обсуждается ниже, то следует вызвать другую сопрограмму, которая использует вычислительные ресурсы вместе с основной программой н выполняет следующие действия: (а) маркирует все )Ч узлов списка АЧАХЬ; (Ъ) маркирует другие узлы, которые свободны для этой программы; (с) связывает все немаркированные узлы вместе для подготовки нового списка АЧА1Ь, который будет использоваться при опустошении текущего списка АЧА11; (сс) сбрасывает маркировочные биты во всех узлах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
