Д. Кнут - Искусство программирования том 1 (1119450), страница 69
Текст из файла (страница 69)
Рассмотрим, однако, более подробно случай, когда таблицы почти полностью занимают память. Тогда алгоритму В. для выполнения перераспределения потребуется очень много времени. Более того, события переполнения (ОЧЕЕРЕОэ) будут происходить все чаще и чаще непосредственно перед исчерпанием памяти. Существует весьма ограниченное количество программ, которые способны работать на грани полного исчерпания памяти и без скорого ее переполнения.
Причем многим программам, которые в таком режиме работы переполняют память, вероятно, приходится тратить огромное количество времени на перераспределение памяти согласно алгоритмам С и В незадолго до полного исчерпания памяти. К сожалению, недостаточно хорошо отлаженные программы часто приводят к быстрому исчерпанию ресурсов памяти. Во избежание таких затрат можно было бы прервать выполнение алгоритма С на шаге СЯ, если ЯОМ меньше значения В ы, которое задается программистом для предотвращения выполнения избыточных операций перераспределения памяти. При наличии большого количества последовательных таблиц с изменяемыми размерами вряд ли стбит надеяться на то, что можно будет использовать доступную память на все 100% и избежать ее переполнения.
Исследование алгоритма С было продолжено Д. С. Вайсом и Д. К. Ватсоном (П. 8. Ж1зе, П. С. ЧЧасэоп, В1Т 16 (1976), 442 — 450). А. С. Френкель предложил использовать пары стеков, которые увеличиваются по направлению друг к другу (А. 8. Ртаепке1, 1пб Ргос. Весгегэ 8 (1979), 9-10). УПРАЖНЕНИЯ 1. (16] Сколько элементов может одновременно находиться в очереди без возникновения переполнения (ОЧЕЕИ.ОЧ) прн выполнении с очередью операций (6, а) и (7, а)7 2. [22] Обобщите метод на основе правил (6, а) и (7, а) так, чтобы он был применим для любого дека с менее чем И элементами. Иначе говоря, предложите правила выполнения двух других операций: "вывод элемента с конца" и "ввод элемента с начала". 3.
[21] предположим, что возможности компьютера и11 расширены следующим образом: 1-пеле каждой инструкции имеет внд 81~+1м где О < 1~ < 8. 0 < Хг < 8. В ассемблере используется команда ОР АООЕЕЯЯ, 1ы 1з нли, как сейчас, Ор АООЕЕЯЯ,1м если 1~ — — О. Она обозначает сначала "модификацию адреса" 1~ для адреса АОПНЕЯЯ, затем — выполнение "модификации адреса" 1г для резулътирующего адреса и, наконец, выполнение операции ОР для нового адреса. При этом модификация адреса определяется следующим образом. О:М=А 1: М = А+г?1 2: М = А+г?2 6; М = А+г16 7: М = резулътирующий адрес, определенный по полям АООВЕЯЯ.1ш?э в ячейке А. ПРи этом не допУскаетсЯ слУчай, когда 1~ -- 1з —— 7 в Ячейке А, (Обоснование этого ограничения приводится в упр.
5.) Здесь А обозначает адрес до выполнения операции, а М вЂ” результат модификации адреса. Во всех случаях результат будет неопределенным, если значение М не умещается в два байта и знаковое поле. Время выполнения увеличивается на одну единицу для каждой выполненной операции "косвенной адресации" (монификация 7). В качестве нетривиального примера предположим, что ячейка памяти 1000 содержит ИОР 1000, 1: 7, ячейка 1001 — ИОР 1000,2, а индексные регистры 1 и 2 — 1 и 2 соответственно.
В таком случае команда 1ОА 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-й элемент из Э-й таблицы в регистр А за счет одной команды, предполагая, что 1 находится в регистре гП, а Э вЂ” в регистре г12? с) Каким будет резулътат выполнения команды ЕМ?4 Х,7, если предположить, что поле (3: 3) в ячейке Х равно нулю? 4.
(ЯБ) Допустим, что возможности компьютера й1Х расширены так, как в упр.3. Покажите, как можно выполнить перечисленные ниже действия с помощью одной команды (со вспомогательными константами). а) Организовать бесконечный цикл за счет непрекращающейся косвенной адресации. Ь) Внести в регистр А значение ПИК(АХИМ(х)), в котором переменная связи х хранится в поле (О: 2) ячейки Х, значение 1.1ИК(х) — в поле (О: 2) ячейки х и т. д., при условии, что поля (3: 3) в этих ячейках равны нулю.
с) Внести в регистр А значение 1.?ИК(ь?ИК(ъ?ИК(х) ) ) при тех же условиях, что и в п. (Ь). 4) Внести в регистр А содержимое ячейки гН + г?2+ г13+ г14+ г15+ г16. е) Умножить на четыре текущее значение регистра г16. б. (36) Предлагаемый в упр, 3 способ расширения возможностей компьютера И1Х содержит нежелательное ограничение, которое запрещает использовать "7:7" в косвенно адресованной ячейке. а) Приведите пример того, что без такого ограничения в компьютере И1Х потребовалось бы на уровне аппаратного обеспечении реализовать большой внутренний стек трехбитовых элементов.
(Даже для такого мифического компьютера, как И1Х, аппаратное обеспечение может оказаться очень дорогим.) Ь) Объясните, почему такой стек не нужен при использовании подобного ограничения. Иначе говоря, создайте такой алгоритм, с помощью которого аппаратное обеспечение компъютера может выполнять нужные модификации адреса без использования дополнительной емкости регистра. с) Найдите менее строгое ограничение, чем предложенное в упр. 3 ограничение для поля 7:7, которое в некоторой степени позволило бы устранить трудности, описанные в упр. 4, (с), а также не требовало дорогостоящего аппаратного обеспечения. 6. [10] Определите, какая из приведенных ниже последовательностей действий может вызвать переполнение или недостаток с начальной конфигурацией памяти, показанной на рнс.
4: (а) 10 (и) 1э, '(с) 1з; (о) 14141л1410 (е) ПэПэ1э1э1ь 7. [12] На шше 64 алгоритма С предусмотрена операция деления на 1ИС. Может ли значение 160 быть равным нулю когда-либо в этом месте данного алгоритма? 8. [66] Объясните, как можно было бы модифицировать, коды (9) и (10), а также алгоритмы переупаковки в случае, когда один нли несколько списков имеют структуру очереди с циркулярным порядком обработки, аналогично правилам (б, а) и (7, а). 9. [М27] Используя математическую модель, описанную почти в самом конце раздела, докажите, что среднее количество перемещений определяется формулой (14).
(Обратите внимание, что для выполнения последовательности действий 1, 1, 4, 2, 3, 1, 2, 4, 2, 1 потребуется О+ О+ О+ 1+ 1+ 3+ 2+ О+ 3+ б = 16 перемещений.) 10. [Мвб] Изменим математическую модель в упр. 9, предположив, что таблицы могут иметь разные размеры. Иначе говоря, предположим, что рь — это вероятность того, что а, = (г для 1 < 1' < т, 1 <?г < п. Таким образом, рг + рэ + .. + р„= 1, а в предыдущем упражнении рассматривался частный случай, когда рь = 1/и для всех lг. Определите среднее количество перемещений, т.
е, укажите, какой будет формула (14) в этом более общем случае. Относительный порядок п списков можно изменить так, что более длинные списки будут располагаться правее (нли левее). При каком относительном порядке и списков среднее количество перемещений будет минимальным для данного набора вероятностей р1, р2,, р 11. [МЗР] Расширим предложенную в упр. 9 задачу следующим условием: для выполнения первых 1 операций вставки в стек не требуется никаких перемещений> тогда как все последующие операции вставки осуществляются так же, как и прежде.
Следовательно, если г = 2, для приведенной в упр. 9 последовательности потребуется выполнить О+ О+О+ О+ О+ 3+ 0+ О+ 3+ 6 = 12 перемещений. Каким будет среднее количество перемещений при таком дополнительном условии? [Это условие приблизительно моделирует поведение алгоритма при наличии в исходном состоянии 1 доступных свобцдных мест в каждом стеке) 12. [Мве] Выгоду от использования в памяти двух таблиц, которые растут по направлению друг к другу, а не занимают отдельные независимые участки памяти, можно в определенной степени оценить количественно. Для этого сначала рассмотрим модель, использованную в упр. 9 с п = 2. Далее предположим, что в каждой из 2 равно- вероятных последовательностей а„ам ..,, а содержится (г~ единиц и /сэ двоек. (Здесь й~ и /сэ соответствуют размерам двух таблиц после полного заполнения памяти. При смежном расположении таблиц данный алгоритм можно с тем же результатом применить к т = 1ч +?гэ ячейкам вместо 2 шах (йп?гэ) ячеек при раздельном распсшожении таблиц.) Каким будет среднее значение шах (йм йэ)? 13.
[НМ42] Величина шах(?гп?гэ) нз упр. 12 будет даже больше, если более крупные флуктуации таблиц будут вызваны не только случайными операциями удаления, но и случайными операциями вставки. Предположим, что прежняя модель изменена таким образом, что с вероятностью р значение последовательности а, интерпретируется, как удаление, а не как вставка, а весь процесс продолжается до тех пор,пока й~ + кг (общее количество используемых ячеек таблицы) не станет равным пь Причем операция удаления нз пустого списка не дает никакого результата. Например, если т = 4, можно показать, что будет получено следующее распределение вероятностей по окончании всего процесса: (йм йэ) = (0,4) (1,3) (2, 2) (3, 1) (4, 0) 1 1 6 — бр+ 2р~ 1 1 с вероятностью 16-12р~4рз ' 4' 16-12р+4рз 4' 16-12р+4рз Такил» образом, прн увеличении р увеличивается и разница между йг и йю Нетрудно показать, что в пределе при стремлении р к единице распределение?сг становится практически равномерным, а предельное значение гоах(йм лз) будет точно равно э гп+ — '[для четных гл].
Такое поведение существенно отличается от рассмотренного в предыдущем примере (когда р = 0). Однако это не так уж и важно, поскольку при приближении р к единице время, необходимое для завершения процесса, будет быстро стремитъся к бесконечности. Сформулированная в этом упражнении задача заключается в исследовании зависимости шах((с1,/гз) от р н т и определении асимптотических формул для заданных значений р (например, р = 1), если ш стремится к бесконечности. Особый интерес представляет з, случай, когда р = —.
14. [НМ4З] Обобщите резулътат упр. 12 для произвольного п > 2, показав, что для фиксированною и и стремящегося к бесконечности т величина ш! т шах(й1,йм...,й ) и х к1()сэ!... йч! гч+ъэ+- тъ„= л ъъъм.-,ь >е имеет асимптотический вид гл/и+с ~/т+ О(1). Определите константы см сз, сэ и сэ. 16. [40] Используя метод Монте-Карло, промоделнруйте работу алгоритма С для разных распределений вставок и удалений. Какой вывод об эффективности алгоритма С можно сделать на основании этих опытов? Сравните его производительность с производительностью другого алгоритма, в котором узлы сдвигаются вверх илн вниз по одному.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
