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