AOP_Tom1 (1021736), страница 117
Текст из файла (страница 117)
В исходной схеме (6) узел с элементом 6 является атомом. а узел с элементом 7'— пустым Списком. Эти два объекта структурно идентичны, поэтому читатель может вполне резонно возразить: "Л зачем вообще нужно было упоминать об атомах?". Без утраты общности можно было бы определить Список всего лишь как "конечную последовательность атомов или Списков, число которых может быть больше нуля или равно нулю" с обычным соглашением о том, что в каждом узле Списка могут, помимо структурной информации, содержаться данные. Эта точка зрения вполне оправданна, а потому понятие "атом" представляется весьма искусственным. Однако для решения проблемы эффективного использования памяти компьютера было бы разумно выделить именно атомы, так как они не подвергаются тем универсальным операциям, которые желательно использовать для обработки Списков.
Можно заметить, что в представлении наподобие (6) в каждом узле-атоме Ь содержится больше места для данных, чем в узле-Списке 7. Кроме того, при использовании заголовков Списков в представлении наподобие (7) для узлов 6 и 7' предъявляются совершенно разные требования к памяти. Таким образом, концепция атомов вводится только для организации эффективного использования памяти компьютера. В типичных Списках содержится гораздо больше атомов, чем в приведенных здесь 'примерах. Примеры (4) — (7) даны лишь для того, .чтобы продекюистрировать возможные усложнения дашюй схемы, а не присущую ей простоту. Список, по сути, представляет собой линейный список, элементы которого могут содержать указатели на другие Списки.
К наиболее распространенным и необходимым операциям со Списками обычно относятся операции с линейными списками (создание и удаление списка, вставка и удаление элементов. расщепление списка, сцепление списков), а также дополнительные операции, которые, прежде всего, интересны при работе с древовидными структурами (копирование, обход, ввод и вывод вложенной информации). Для этого можно использовать любой нз трех основных методов представления в памяти связанных линейных списков, а именно: обычный, циклический или дважды связанный список. В зависимости от используемого алгоритма эти способы представления могут иметь разные степени эффективности.
Структура на схеме (7) с использованием этих типов списков в памяти компьютера может иметь следующее представление, Деажди еееоанний список 1ИРО 951ИК ШИК 81.1ИК Адрес Обмчмий список 1ИГО 911ИК Кь1ИК Циклический список 1ИРО Ж1ИК 811ИК Здесь ЕЕ1МК используется для левого указателя в дважды связанном списке. Поля 1МРО и ОЕ1МК одинаковы для всех трех типов списков. Нет необходимости повторять алгоритмы обработки Списков для любого из этих трех типов представления, так как они уже неоднократно обсуждались. Отметим лишь важные различия между Списками и более простыми типами списков, которые рассматривались выше. 1) В описанном выше типе представления в памяти узлы-атомы отличаются от других атомов.
Более того, при использовании циклических и дважды связанных списков узлы-заголовки списков, которые применяются для упрощения обхода Списков, желательно отличать от других узлов. Поэтому каждый узел обычно имеет поле ТУРЕ, в котором хранятся сведения о типе содержащихся в узле данных. Поле ТУРЕ часто используется для того, чтобы можно было различать разные типы атомов (например, символьные величины, целочисленные величины либо числа с плавающей запятой при их обработке или отображении). 2) Формат узлов при выполнении общих операций со Списками в компьютере М11 может быть представлен следующими двумя способами. а) Однословный формат, в котором все данные (1МРО) содержатся в следующих атомах: (9) Я Т МЕР КЕ1МК Знак гсокращеиие от слова нв1бпо), т. е.маркировочный бит, исполь- зуемый при сборке мусора (см.
ниже) Тип (сокращение от слова "суре"), т. е. Т = О для заголовка Списка, Т =.1 для элемента подСписка и Т > 1 — для атомов 010: — Заголовок 020 020: а 060 030 030: 6 Атом 040 040: с 090 050 050; е 010 Л 060: — Заголовок 070 070: 1 110 080 080: д 120 Л 090: — Заголовок 100 100: д 060 Л 110: — Заголовок Л 120: — Заголовок 130 130: Й 010 140 140: ,1 060 Л вЂ” Заголовок 020 а 060 030 6 Атом 040 с 090 050 е 010 010 — Заголовок 070 110 080 д 120 060 — Заголовок 100 д 060 090 — Заголовок 110 — Заголовок 130 Л 010 140 7' 060 120 — Заголовок а 060 Ь Атом с 090 е 010 — Заголовок 110 д 120 — Заголовок д 060 — Заголовок — Заголовок 6 010 060 ОоО 010 020 030 040 080 060 070 100 090 110 140 120 130 020 030 04О Ооо 010 ОУО <8) 080 060 100 090 110 130 140 120 ВЕР: Если Т = О, тр ВЕР— -счетчик ссылок (см.
ниже); если Т = 1, то ЕЕГ указывает на заголовок Списка рассматриваемого подСписка; если Т > 1, то КЕР указывает на узел, в котором содержатся маркировочный бит и 5 байт атомарной информации Ы.ТИК: Указатели, используемые в обычном или циклическом списке (8) Ь) Двухсловный формат: В Т ШИК ИЬ1ИК (10) 1ИРО Е,Т: То же, что в (9) ШИК, ЕЕ1ИК: Обычные указатели, которые используются в дважды связанных списках (8) 1ИЕО: Полное слово с данными узла; в узле-заголовке оно может содержать счетчик ссылок; текущий указатель на внутренний компонент Списка, используемый для упрощения линейного обхода Списка; символьное имя н т. д. Если Т = 1, то в нем содержится также поле 1И.1ИК 3) Ясно, что Списки представляют собой структуры очень общего типа.
Действителыю, по-видимому совершенно справедливо утверждение о том, что любую структуру какой бы она ни была, можно представить в виде Списка, учитывая соответствующие соглашения. Благодаря такой универсальности Списков для упрощения работы с ними было разработано множество систем программирования. Причем для компьютера практически любого типа обычно существует сразу несколько таких систем. Они основаны на универсальном формате узлов, например на таком, как показано выше, на схемах (9) и (10), которые созданы специально для более гибкой организации операций со Списками. На самом деле ясно, что обычно такой универсальный формат — не самое лучшее решение какой-либо конкретной проблемы, поэтому уннверсальные программы выполняются значительно медленнее, чем система с настройками для конкретной задачи. Например, легко видеть, что если бы мы использовали универсальное представление Списка типа (9) или (10) практически во всех приложениях, с которыми нам приходилось работать до сих пор в этой главе, вместо принятого в них формата узлов, это существенно усложнило бы их код.
Часто при обработке узлов Списка необходимо проверять содержимое поля Т, что не требовалось в любой из перечисленных выше программ. Эта потеря эффективности при использовании универсальной системы во многих случаях компенсируется сравнительной простотой программирования и сокращением времени отладки.
4) Существует также чрезвычайно важное различие между алгоритмами обработки Списков и алгоритмами, приведенными выше в этой главе. Так как один Список может содержаться сразу в нескольких Списках, совершенно неясно, когда его следует вернуть в пул свободной памяти. До сих пор в наших алгоритмах всякий раз, когда узел КОРЕ(Х) уже не был нужен, упоминалась команда "АЧА1Ь ~м Х". Но поскольку во время работы Списки общего типа могут генерироваться и удаляться совершенно непредсказуемым образом, то часто очень трудно сказать, когда у зел уже не нужен. Следовательно, задача поддержания списка свободного пространства существенно усложняется при работе со Списками. чем при возникновении более простых случаев, которыя рассматривались выше. Остальная часть этого раздела посвящается именно проблеме удаления неиспользуемых элементов и увеличения размера свободной памяти (эьогабе тес!ашабоп ргоЫеш).
Допустим, что нужно создать универсальную систему обработки Списков, которая будет применяться сотнями программистов. Для обслуживания списка свободной памяти существует два основных метода: счетичикое ссылок (геуегепсе соипгегг) и сборки мусора (уагбаде сойессгоп). В методе на основе счетчиков ссылок в каждом поле используется новое поле с числом стрелок, которые уйазывают на этот узел.
Показания такого счетчика легко отслеживать во время выполнения программы: при его обнуления узел можно поместить в список свободной памяти. С другой стороны, для метода сборки мусора требуется дополнительное однобитовое поле на каждом узле под названием маркироеочный бит (тлагй 6й). Основная идея в этом случае заключается в следующем: необходимо определить почти все алгоритмы так, чтобы они не возвращали неиспользуемые узлы в список свободной памяти сразу же. Пусть программа спокойно выполняется до тех пор, пока не будет израсходовано все свободное пространство в памяти.
После этого специальный алгоритм "регенерации памяти" использует маркировочные биты для определения неиспользуемых в данный момент узлов и их возврата в список свободной памяти, после чего программа сможет продолжить свою работу. Ни один из этих двух методов не является удовлетворительным. Основным недостатком метода счетчиков ссылок заключается в том, что не всегда удается освободить все неиспользуемые узлы. Он прекрасно подходит для перекрывающихся Списков (Списки могут содержать подСписки общего типа), но рекурсивные Списки наподобие Т, и Х из (4) никогда не будут возвращены в список свободной памяти с помощью метода счетчика ссылок.
Их счетчики будут всегда ненулевыми (поскольку они ссылаются на самих себя), даже если никакие другие Списки во время работы программы на них не указывают. Более того, для применения метода на основе счетчиков ссылок требуется использовать значительную часть памяти (хотя это пространство иногда все равно не используется из-за размера компьютерного слова). Трудности, возникающие при использовании метода сборки мусора, связаны не только с нежелательной утратой одного бита в каждом узле, но и с тем, что он работает очень медленно прн почти полном заполнении памяти.
Причем в таких случаях количество найденных свободных ячеек памяти не оправдывает затраченных на это усилий. Программы, требующие больше свободной памяти (так происходит со многими не до конца отлаженныл1и программами), часто очень неэкономно расходуют время при многократных вызовах программ сборки мусора, которые становятся почти бесполезными по мере исчерпания свободной памяти. Частичное решение этой проблемы заключается в том, что программист указывает некоторое значение й и работа прекращается, если в результате сборки мусора было найдено 6 или меньше неиспользуемых узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
