Д. Кнут - Искусство программирования том 1 (1119450), страница 82
Текст из файла (страница 82)
Верно ли, что САььСАЕ[Рь005) или САььОР [РьООЕ) ~ О? Если неверно, то верно ли, что РьООЕ = 2? Если неверно, то верно ли, что САШ>ОНИ [91005) ~ О? Если неверно, повторить шаг Е7. ЕУ. Установка ин икато а беэ ействня. (См. строку 202.) 02 <- О. Выполнить подпрограмму ОЕС131ОМ. Вернуться к моделированию других событий. 1 критические моменты; именно с ее помощью бьша подготовлена табл. 1. Эти подробности здесь опущены; они довольно просты, но в значительной мере усложняют код.
Было создано иескопько языков программирования, которые позволяли упростить форму указиэия действий дискретного моделирования с последующей компиляцией этих указаний на машинный язык. Б данном разделе язык ассемблера использовался, конечно же, потому, что здесь рассматривались основные методы управления связанными списками и подробности дискретного моделирования на компьютере, который способен выполнять последовательные, а не параллельные вычисления. Метод управления последовательностью сопрограмм на основе списка ЧА1Т или перечня действий, который описан в этом разделе, называется квазипараллельной обработкой (уиаемрагайе1 ргосеэзэпу). Анализ времени выполнения такой длинной программы сделать довольно трудно, потому что она пронизана весьма сложными взаимосвязями. Однако большие программы часто тратят ббльшую часть времени на выполнение сравнительно небольших процедур, которые осуществляют простые действия.
Поэтому хорошую оценку общей производительности можно получить с помощью особой процедуры трассировки, или, иначе говоря, с помощью про1байлера (рго7э)ег), которая выполняет программу и записывает, как часто выполняется та или иная команда. Она позволяет обнаружить "уязвимые места" производительности программы, которым следует уделить особое внимание.
[См. упр. 1.4.3.2-7. См. также Бойщаге Ргасйсе Зг Ехреп'- епсе 1 (1971), 105-133, где приводятся примеры таких исследований для программ на языке гОВТВА;ч, произвольно выбранных из мусорных корзин Станфордского компьютерного центра (БьапГогс) Сошрптег Сеп1ег).] Автор экспериментировал с программой моделирования работы лифта, запуская ее в течение 10000 единиц по моделируемой шкале времени и при условии, что в модели находится 26 человек. Оказалось, что наиболее часто выполнялся цикл сортировки БОЕТ19, строки 073 — 075, а именно — 1432 раза, тогда как процедура сортировки БОЕТ19 вызывалась 437 раз.
Процедура СТАЕ выполнялась 407 раз, поэтому для увеличения скорости ее выполнения не следовало бы вызывать подпрограмму ВЕЕЕТЕ9 в строке 095; лучше полностью включить в программу четыре строки этой подпрограммы (с экономией 4и при каждом использовании СУСЕЕ). С помощью профайлера также было обнаружено, что подпрограмма ВЕС1Б10й вызывалась только 32 раза, а цикл на шаге Е4 (строки 217 — 219) выполнялся всего 142 раза. Автор надеется, что при изучении этого примера читатель узнает столько же нового о моделировании, сколько автор узнал о работе лифтов.
УПРАЖНЕНИЯ 1. (21] Предложите описание операций вставки и удаления данных с левого конца дважды связанного списка (1). (С учетом тех же операций на правом конце, которые можно вывести из соображений симметрии, получим описание всех действий лля дека общего типа ) 2. (22] Объясните, почему для одиосвязного списка нельзя выполнять операции так же эффективно, как для дека общего типа Удаление элементов может быть эффективно выполнено только с одного конца одиосвязиого списка ° 3.
[22] В модели работы лифта из данного раздела для каждого этажа используются три переменные вызова (САШЗР, САЫ.САк и САУЛ.РОИН), которые представляют нажимаемые кнопки. Вполне возможно, что вместо трех лифту необходима только одна или две двоичные переменные для кнопок вызова на каждом этаже, Объясните, в какой последовательности экспериментатор должен нажимать кнопки в данной модели, чтобы доказапьь, что для каждого этажа (за исключением самого нижнего и самого верхнего) существуют три независимые двоичные переменные.
4. (24] Шаг Е9 в сопрограмме работы лифта обычно отменяется на шаге Еб; даже если он не отменен, он выполняет не очень большой объем работы. Объясните, при каких обстоятельствах лифт будет вести себя иначе, если шаг Е9 удалить из модели. Например, может ли лифт иногда останавливаться на этажах в другом порядке? б. (20] В табл. 1 человек 10 появляется на этаже 0 в момент 1048. Покажите, что, если бы человек 10 появился на этаже 2, а не на этаже О, лифт отправился бы вверх, а не вниз после входа всех людей в кабину на этаже 1 несмотря на то, что человек 8 желает спуститься на этаж О. 6.
[2Я] В период 1183 — 1233 в табл. 1 пассажиры 7-9 входят в кабину лифта на этаже 1; лифт спускается на этаж О, и из него выходит только пассажир 8. Затем лифт снова останавливается на этаже 1, предположительно для того, чтобы взять пассажиров 7 и 9, которые уже находятся в кабине лифта; таким образом, на этаже 1 лифт уже никто не ожидает. (Эта ситуация возникает в Квлтехе довольно редко; если вы вошли в лифт, движущийся в ненужном вам направлении, вам придется снова сделать дополнительную остановку на пути к исходному этажу.) Во многих других типах лифтов пассажиры 7 и 9 не были бы взяты в лифт в момент 1183, так как индикаторы снаружи лифта показали бы, что он движется вниз, а не вверх.
Им пришлось бы ожидать возвращения лифта. В описанной модели такие индикаторы не предусмотрены, а потому невозможно сказать, в каком направлении будет двигаться лифт, до тех пор, пока человек не попадет в кабину. Следовательно. табл 1 отражает реальную ситуацию. Какие изменения необходимо внести в сопрограммы П и Е, чтобы в описанной выше модели лифта использовались внешние индикаторы, благодаря которым людям не приходилось бы входить в кабину лифта, следующего в противоположном направлении". 7. (25] Часто программистам очень стыдно признавать свои ошибки в программах, но, если ошибки поучительны, о них не следует забывать; лучше сообщить о приобретенном опыте другим.
При создании программы из этого раздела автор совершил (среди прочих) следующую ошибку. строка 1о4 содержала команду "ЛА83 СУС1.8" вместо "ЛАНЕ 04А". Действительно, если лифт прибыл на этаж, нужный конкретному человеку, то больше нет необходимости "отменять" шаг С4. Поэтому можно просто перейти к процедуре СТСОЕ и продолжить моделирование других действий. В чем же заключается ошибка? 8. (21] Создайте код для выполнении шага Е8, строки 277 — 292, который опущен в программе из данного раздела.
9. (22] Создайте код для подпрограммы РЕС13108, который опущен в программе из данного раздела. 10. (40] Вероятно, здесь стоит отметить,что, хотя автор пользовался лифтом в течение многих лет и думал, что довольно хорошо знает принцип его работы, только во время написания этого раздела он обнаружил новые факты об алгоритме выбора направления движения реального лифта. Шесть раз автору приходилось экспериментировать с лифтом, и всякий раз он думал, что уж теперь-то он окончательно понял его твори ореганй.
(Теперь автор не склонен к продолжению этих экспериментов, так как опасается, что во время нового эксперимента обнажится еще одна новая грань поведения лифта, которая будет противоречить предложенному здесь варианту алгоритма.) Мы часто склонны недоопенивать степень непонимания предмета, но лишь до тех пор, пока не попытаемся промоделировать его с помощью компьютера. Попробуйте описать действия некоторого хорошо знакомого вам лифта Проверьте свой алгоритм с помощью экспериментов (подглядывать в его электрическую схему— нечестно'), а затем создайте дискретную модель этой системы и запустите ее на компьютере ь 11. (21) (Фрагггеншарно обноеллемал памлтиь.) Следующая проблема часто возникает в задачах синхронного моделирования Система имеет п переменных Ч[1],.,Ч[п], и на каждом шаге моделирования новые значения некоторых из них вычисляются на основе прежних Предполагается, что вычисления выполняются "одновременно" в том смысле, что эти переменные не принимают новых значений до тех пор, пока не будут выполнены все операции присвоения, Таким образом, одновременное появление выражений ЧП3 е — Ч[23 и Ч[23 г- у[13 приведет к обмену значениями Ч[П и у[23, это сильно отличается от того, что обычно происходит при последовательном вычислении Эту ситуацию, конечно же, можно промоделировать с помощью таблицы ЯЕНЧ [И, НЕНЧ[п].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
