Д. Кнут - Искусство программирования том 1 (1119450), страница 70
Текст из файла (страница 70)
16. [20] В этом разделе описан способ более эффективною использования общей области памяти благодаря такому расположению двух стеков в памяти, при котором они могут расти навстречу друг другу. Можно ли так расположить две очереди или стек и очередь, чтобы добиться такой же эффективности прн использовании общей области памяти? 17. [00] Если п — это произвольная последовательность вставок и удалений типа (12), пусть эо(и) — количество переполнений стека, которые возникают после применения про- стого способа, показанного на рнс.
4, к этой последовательности и с начальными условиями наподобие (11), а в1(а) — соответствующее количество переполнений по отношению к другим начальным условиям наподобие (13). Докажите, что во(п) < э1(п) + 1 — 1о. ь 18. [МЮО] Покажите, что общее время выполнения любой послейователъности т вставок и/или удалений согласно алгоритмам С и 31 имеет порядок 0(т + и 3 ...оъ/(1 — оъ)), где оь — доля памяти, занятая во время погледней переупаковки памяти до /г-й операции.
пъ = 0 до первой переупаковки памяти. (Следователъио, если память никогда не запол- няется более чем на 90%, для выполнения каждой операции потребуется не больше 0(п) тактов независимо от общего размера памяти.) Предполагается, что 1 — |о > пз.
ь 19. [10] (Нуль-нндексироеанпе.) Опытным программистам известно, что в общем случае для индексирования элементов линейного списка лучше использовать форму Х [03, Х[13, ..., Х [и — 13 вместо традиционной формы Х И3, Х [23,, Х [п3. Тогда, например, базовый адрес бо в (1) будет указывать на наименьшую ячейку массива. Измените методы вставки и удаления (2, а), (3, а), (6, а) и (7, а) для стеков и очередей так, чтобы они соответствовали этому соглашению. Иначе говоря, измените их так, чтобы все элементы списка находились в массиве Х [03, Х [13,, Х[М вЂ” 13, а не в массиве Х [13, Х[23, ..., Х [63. 2.2.3.
Связанное распределение Вместо того чтобы хранить линейный список в последовательных ячейках памяти, можно использовать более гибкую схему, в соответствии с которой каждый узел содержит связь со следующим узлом списка. Связанное распределение Адрес Содержимое Последовательное распределение Адрес Содержимое Ъе+ с: бе+ 2с: Ьо+Зс: То+ 4с: Ьо+ 5с; А: В: Здесь А, В, С, Р и Š— это произвольные ячейки памяти, а Л вЂ” пустая связь (см. раздел 2.1). В программе с такой таблицей с последовательным распределением элементов для обозначения ее длины (5 элементов) потребуется либо дополнительная переменная нли константа, либо специальный код в последнем, 5-м, элементе или в следующей за ним ячейке памяти.
В программе со связанным распределением необходимо использовать переменную или константу связи, которая будет указывать на адрес А, причем все другие элементы списка могут быть найдены с помощью этого адреса. Как упоминалось выше, в разделе 2.1, связи часто схематически изображают в виде стрелок, так как их действительное расположение в памяти обычно не имеет никакого значения. В таком случае описанная выше таблица при связанном распределении памяти будет выглядеть следующим образом. Р1ЭЗТ Элемент 1 Элемент 2 Элемент 3 Элемент 4 Элемент Э (1) Здесь РХВБТ вЂ” это переменная связи, которая указывает на первый узел списка.
Сравнив два основных типа хранилищ, можно сделать несколько очевидных выводов. 1) При организации связанного распределения в памяти потребуется выделить дополнительное пространство для размещения связей. В некоторых ситуациях этот фактор может оказаться доминирующим. Но часто бывает так, что хранимая в узле информация все равно не занимает все слово целиком, поэтому место для связи всегда найдется.
Кроме того, во многих случаях несколько элементов комбинируются в одном узле, а потому связь может использоваться сразу для нескольких элементов данных (см. упр. 2.5 — 2). Однако важнее то, что с помощью связанного распределения памяти выигрыш можно получить неявно за счет частичного перекрытия таблиц, совместно использующих некоторые области памяти. Часто последовательное распределение не так рационально, как связанное, поскольку для его эффективной. работы необходимо очень большое количество дополнительных вакантных ячеек памяти.
Так, в конце предыдущего раздела уже объяснялось, почему подобные системы становятся крайне неэффективными при плотном заполнении памяти. 2) Операция удаления элемента в связанном списке выполняется проще. Например, для удаления элемента 3 необходимо только изменить связь с ним в элементе 2. А при последовательном выделении памяти такое удаление в общем случае подразумевает перемещение значительной части списка в другие ячейки. 3) При использовании схемы связанного распределения памяти проще выполняется и вставка элемента в середину списка. Например, для вставки элемента 2- в 1 список (1) потребуется изменить только две связи. УПИТ Элемент 1 Элемент 2 Элемент 3 Элемент 4 Элемент 5 Элемеит 22 (2) А при работе с длинной таблицей с последовательным выделением памяти лля вставки нужно будет выполнить гораздо больше действий, для чего потребуется чрезвычайно много времени.
4) Обращения к произвольным элементам списка гораздо быстрее осуществляются при последовательном выделении памяти. Для доступа к л-му элементу списка, где Й вЂ некотор переменная, в случае последовательного распределения памяти потребуется фиксированное время, но для доступа к нужному элементу в случае связанного распределения памяти потребуется выполнить я итераций. Таким образом, полезность связанного распределения памяти основывается на том, что в большинстве приложений доступ к элементам списка выполняется в последовательном, а не произвольном порядке. Для доступа к элементам в середине или в конце списка можно создать дополнительную переменную связь или целый список переменных связи, которые указывают на нужные позиции списка. 5) В схеме связанного распределения памяти проще организовать объединение двух списков или разбиение списка на два других списка, которые могут увеличиваться независимо.
6) Схема связанного распределения памяти прекрасно подходит для организации более сложных структур, чем простые линейные списки, Например, ее можно применить для создания переменного количества списков переменного размера. Причем каждый узел одного из них может быть началом другого списка, к тому же узлы могут быть связаны между собой несколькими способами и образовывать другие списки и т, д. 7) Такие простые операции, как последовательная обработка элементов списка, на многих компьютерах выполняется немного быстрее.
Для компьютера И11 операторы 1МС1 с и Ы1 0,1(1.1МК) отличаются только одним тактом, но на многих компьютерах не реализована возможность загрузки индексного регистра из индексированной ячейки. Если элементы связанного списка принадлежат разным страницам устройства хранения большого объема, то операция доступа к ним может выполняться значительно дольше.
Таким образом, технология связанного распределения памяти позволяет обойти ограничения, наклвдываемые последовательной природой компьютерной памяти. При выполнении одних операций она способствует достижению гораздо более высокой эффективности, а при выполнении других, наоборот, снижает ее. Обычно совершенно ясно, какая технология лучше всего подходит в конкретной ситуации. Поэтому часто в одной и той же программе используют списки разных типов.
В следующих нескольких примерах предположим для удобства, что узел состоит из одного слова, которов содержит два поля — 1МГО и Ь1МК: (3) 1МРО Ь1МК При использовании связанного распределения памяти обычно подразумевается, что существует некоторый механизм поиска свободного места для нового узла при вставке новых данных в список. Это обычно выполняется с помощью специального списка свободного пространства. Здесь он будет называться списком АЧА1Ь (или стеком АЧА1Ь, поскольку он обычно обрабатывается, как стек магазинного типа, т.
е. по принципу "последним вошел — первым вышел" ()аэгйп-бгэыопг)). Набор всех неиспользуемых в данный момент узлов связан в список, который устроен так же, как и все другие списки. Переменная связи АЧА1Ь ссылается на самый верхний элемент этого списка. Таким образом, если необходимо присвоить переменной связи Х адрес нового узла, а сам узел зарезервировать для дальнейшего использования, то можно выполнить следующие действия: (4) Х +- АЧАП„ АЧА1Ь ~ — 1.1МК(АЧАП.).
При этом из стека АУА1Ь будет удален самый верхний элемент, а Х будет указывать на только что удаленный узел. Операция (4) в дальнейшем будет использоваться настолько часто, что для нее лучше ввести специальное обозначение: Х «м АЧАЬЬ будет означать, что Х указывает на новый узел. Для удаления ненужного узла операцию (4) можно обратить: (5) 1.1МК(Х) < — АЧАП., АЧАП.
+- Х. При этом узел с адресом, указанным с помощью Х, будет возвращен в список свободного пространства, а вся операция (5) будет обозначаться как АЧАЬЬ с:= Х. При обсуждении правил работы со стеком АЧА1Ь были опущены некоторые важные подробности.
Например, ничего не было сказано о его создании после запуска программы. Очевидно, что стек может быть создан следующим образом: (а) за счет связывания всех узлов, которые предполагается использовать для организации связанной памяти, (Ь) путем присвоения адреса первого из этих узлов переменной связи АЧА1Ь и (с) в результате присвоения значения Л связи последнего узла. Набор всех выделенных таким образом узлов называется пулом (йогаде роо(). Однако самой важной особенностью новой структуры является проверка переполнения. В операции (4) не предусмотрена проверка ситуации, когда в памяти исчерпано все свободное пространство. На самом деле для этого операция Х ~ АЧАЬЬ должна быть определена иначе: Если АЧАП, = Л, то ОЧЕКУЬОЫ; в противном случае Х < — АЧА1Ь, АЧА1Ь <- Ь1МК(АЧА1Ь).
(5) Возможность переполнения должна быть предусмотрена всегда! В данной ситуации переполнение (ОЧЕКГЬОМ) означает либо прекращение работы программы (к сожалению), либо запуск процедуры "сборки мусора" (КагЬайе сойесйоп), которая предпримет попытку поиска свободного пространства.
Сборка мусора более подробно описывается в разделе 2.3.5, Для управления стеком АУА15 можно использовать другую технологию, поскольку часто заранее неизвестно, какой объем памяти потребуется для пула. Для этого можно применить последовательную таблицу переменного размера, которая может сосуществовать в памяти вместе со связанными таблицами. В таком случае нужно позаботиться о том, чтобы связанная область памяти не занимала больше места, чем необходимо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
