AOP_Tom1 (1021736), страница 71
Текст из файла (страница 71)
9. В таком случае среднее количество необходимых операций перемещения равно (14) Таким образом, как и следовало ожидать, количество операций перемещения прямо пропорционально квадрагпп количества последовательных увеличений размера таблицы. То же самое верно и для отдельных стеков с неравиовероятными реализациями (см.
упр. 10). На основе этого анализа можно сделать следующий вывод: при значительном количестве операций встайки элементов в таблицы количество перемещений может быть очень большим. Это своеобразная компенсация за возможность компактной упаковки большого количества последовательных таблиц. Для анализа алгоритма С до сих пор не предложено ни одной теоретической модели, и маловероятно,что какая-либо простая теория сможет адекватно описать характеристики реальных таблиц при таких условиях работы.
Однако в упр. 18 предлагается анализ самого неблагоприятного случая с оценкой времени выполнения, которое будет не таким большим, если память исчерпана не полностью. Как показывает опыт, при заполнении памяти наполовину (т. е. когда доступная область занимает половину всей памяти) с помощью алгоритма С перераспределение памяти нужно выполнить лишь в незначительней степени. Здесь важно отметить, что этот алгоритм эффективен при заполнении памяти наполовину, а при практически полном заполнении, по крайней мере, можно достоверно оценить его эффективность.
Рассмотрим, однако, более подробно случай, когда таблицы почти полностью занимают память. Тогда алгоритму К для выполнения перераспределения потребуется очень много времени. Более того, события переполнения (ОРЕЕРЬОЕ) будут происходить все чаще и чаще непосредственно перед исчерпанием памяти. Существует весьма ограниченное количество программ, которые способны работать на грани полного исчерпания памяти и без скорого ее переполнения. Причем многим программам, которые в таком режиме работы переполняют память, вероятно, приходится тратить огромное количество времени на перераспределение памяти согласно алгоритмам С и Н.
незадолго до полного исчерпания памяти. К сожалению, недостаточно хорошо отлаженные программы часто приводят к быстрому исчерпанию ресурсов памяти. Во избежание таких затрат можно было бы прервать выполнение алгоритма 0 на шаге ОЗ, если ЯЯМ меньше значения окнш которое задается программистом для предотвращения выполнения избыточных операций перераспределения памяти. При наличии большого количества последовательных таблиц с изменяемыми размерами вряд ли стбит надеяться иа то, что можно будет использовать доступную память на все 100% и избежать ее переполнения. Исследование алгоритма С было продолжено Д. С. Вайсом и Д.
К. Ватсоном (В. Б. %1эе, В. С. ЪЧа1эоп, В1Т 16 (1976), 442 — 450). А. С. Френкель предложил использовать пары стеков, которые увеличиваются по направлению друг к другу (А. Б. Ргаеп(се1, 1пб Ргос. Ъе1сегэ 8 (1979), 9-10). УПРАЖНЕНИЯ 1. (15) Сколько элементов может одновременно находиться в очереди без возникновения переполнения (ОРЕЕРЬОя) при выполнении с очередью операций (б, а) и (7, а)? 2. [22) Обобщите метод на основе правил (8, а) и (7, а) так, чтобы он был применим для любого дека с менее чем н элементами. Иначе говоря, предложите правила выполнения двух других операций: "вывод элемента с конца" и "ввод элемента с начала". 3. (21) Предположим, что возможности компьютера И11 расширены следующим образом: 1-поле каждой инструкции имеет вид 81~+1м где 0 < 1~ < 8,, 0 < 1э < 8.
В ассемблере используется команда 0Р А00ЕЕЯЯ,1ы1э или, как сейчас, 0Р А008288,1к если 1~ = О. Она обозначает сначала "модификацию адреса" 1~ для адреса А00ВЕЯЯ, затем — выполнение "модификации адреса" 1т для результирующего адреса и, наконец, выполнение операции ОР для нового адреса. При этом модификация адреса определяется следующим образом. О:М=А 1:М=А+гП 2: М = А + г12 6: М = А + г16 7: М = результирующий адрес, определенный по полям АООЕЕЯЯ,1ы1э в ячейке А. При этом не допускается случай, когда 1~ = 1г = 7 в ячейке А. (Обоснование этого ограничения приводится в упр. 5.) Здесь А обозначает адрес до выполнения операции, а М вЂ” результат модификации адреса.
Во всех случаях результат будет неопределенным, если значение М не умещается в два байта и знаковое поле. Время выполнения увеличивается на одну единицу для каждой выполненной операции "косвенной адресации" (модификация 7). В качестве нетривиального примера предположим, что ячейка памяти 1000 содержит ИОР 1000, 1: 7, ячейка 1001 — ИОР 1000,2, а индексные регистры 1 и 2 — 1 и 2 соответственно. В таком случае команда 10А 1000,7:2 эквивалентна команде ЮА 1004, так как 1000.7:2 = (1000,1:7),2 ж (1001.7),2 = (1000,2)„2 = 1002,2 = 1004. а) Используя эти средства косвенной адресации (если это необходимо), покажите, как упростить код в правой части выражений (8), чтобы экономить па две команды при каждом обращении к таблице. Насколько эффективнее будет этот код по сравнению с кодом (8)? Ь) Допустим, имеется несколько таблиц, базовые адреса которых хранятся в позициях ВАЯЕ+ 1, ВХЯЕ+ 2, ВАЯЕ+ 3, ....
Как, используя средства косвенной адресации, можно перенести 1-й злемент из 3-й таблицы в регистр А за счет одной команды, предполагая, что 1 находится в регистре г11, а 3 — в регистре г12? с) Каким будет результат выполнения команды ЕИТ4 Х, 7, если предположить, что поле (3: 3) в ячейке Х равно нулю? 4. (25] Допустим, что возможности компьютера И1Х расширены так, как в упр. 3. Покажите, как можно выполнить перечисленные ниже действия с помощью одной команды (со вспомогательными константами). а) Организовать бесконечный цикл за счет непрекращающейся косвенной адресации. Ь) Внести в регистр А значение ЫИХ(ЫИХ(х) ), в котором переменная связи я хранится в поле (О:2) ячейки Х, значение ЫИХ(х) — в поле (О: 2) ячейки х и т.
д., при условии, что поля (3: 3) в этих ячейках равны нулю. с) Внести в регистр А значение ЫИХ(ЫИХ(ЫИХ (х) ) ) при тех же условиях, что и в п. (Ь). б) Внести в регистр А содержимое ячейки гП + г12 + г13 + г14 + г15 + г16. е) Умножить на четыре текущее значение регистра г16. б. ]ЗБ] Предлагаемый в упр. 3 способ расширения возможностей компьютера ИХХ содержит нежелательное ограничение, которое запрещает использовать "7:7" в косвенно адресованной ячейке. а) Приведите пример того, что без такого ограничения в компьютере И1Х потребовалось бы на уровне аппаратного обеспечения реализовать большой внутренний стек трехбитовых элементов.
(Даже для такого мифического компьютера, как И1Х, аппаратное обеспечение может оказаться очень дорогим.) Ь) Объясните, почему такой стек не нужен при использовании подобного ограничения. Иначе говоря, создайте такой алгоритм, с помощью которого аппаратное обеспечение компьютера может выполнять нужные моднфиквции адреса без использования дополнительной емкости регистра. с) Найдите менее строгое ограничение, чем предложенное в упр.
3 ограничение для поля 7: 7, которое в некоторой степени позволило бы устранить трудности, описанные в упр. 4, (с), а также не требовало дорогостоящего элпаратного обеспечения. 6. [10] Определите, какая из приведенных ниже последовательностей действий может вызвать переполнение или недостаток с начальной конфигурацией памяти, показанной на рис. 4: (а) 1ц (Ь) 1сб (с) 1з; (и) 1~1а141414; (е) ПзПз1з1з1з. 7. [12] На шаге С4 алгоритма С предусмотрена операция деления на 180.
Может ли значение 190 быть равным нулю когда-либо в этом месте данного алгоритма? 8. [Яб] Объясните, как можно было бы модифицировать, коды (9) и (10), а также алгоритмы переупаковки в случае, когда один или несколько списков имеют структуру очереди с циркулярным порядком обработки, аналогично правилам (б, а) и (7, а). 9. [М27] Используя математическую модель, описанную почти в самом конце раздела, докажите, что среднее количество перемещений определяется формулой (14).
(Обратите внимание, что для выполнения последовательности действий 1, 1, 4, 2, 3, 1, 2, 4, 2, 1 потребуется О+ О+ О+ 1+1+ 3+ 2 ч-0+ 3+ б = 16 перемещений.) 10. [М23] Изменим математическую модель в упр. 9, предположив, что таблицы могут иметь разные размеры. Иначе говоря, предположим, что рь — это вероятность того, что а, =?с для 1 < 1 < пз, 1 < к < и. Таким образом, р~+рз+ +р = 1, а в предыдущем упражнении рассматривался частный случай, когда рь = 1/и для всех (с. Определите среднее количество перемещений, т. е, укажите, какой будет формула (14) в этом более общем случае.
Относительный порядок и списков можно изменить так, что более длинные списки будут располагаться правее (или левее). При каком относительном порядке п списков среднее количество перемещений будет минимальным для данного набора вероятностей рпрз - р. 11. [МЯО] Расширим предложенную в упр. 9 задачу следующим условием; для выполнения первых 1 операций вставки в стек не требуется никаких перемещений, тогда как все последующие операции вставки осуществляются так же, как и прежде. Следовательно, если 1 = 2, для приведенной в упр, 9 последовательности потребуется выполнить О+ О+ О+ О+ О+ 3+ 0+ 0+ 3+ б = 12 перемещений.
Каким будет среднее количество перемещений при таком дополнительном условии? [Это условие приблизительно моделирует поведение алгоритма при наличии в исходном состоянии 1 доступных свободных мест в каждом стеке.] 12. [Мке] Выгоду от использования в памяти двух таблиц, которые растут по направлению друг к другу, а не занимают отдельные независимые участки памяти, можно в определенной степени оценить количественно. Для этого сначала рассмотрим модель, использованную в упр. 9 с и = 2. Далее предположим, что в канской из 2 равновероятпых последователыюстей амаю...,а,„содержится?г~ единиц н йз двоек. (Здесь ?с~ и?са соответствуют размерам двух таблиц после полного заполнения памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
