AOP_Tom1 (1021736), страница 84
Текст из файла (страница 84)
1 Приведенная выше программа прекрасно моделирует работу лифта, но выполнять ее бесполезно, поскольку она не выводит никаких выходных данных! На самом деле автор добавил в нее подпрограмму РВТМТ, которая вызывалась в наиболее 26У 153 256 Е58 153 251 50А 252 1А3 252 ЕИТ5 256 1НР 255 БТЗ 256 ЕМТ6 257 БИТА 252 15М 259 ЕТА 1НР 260 Е7 1ИС4 261 ЕМТА 262 1НР 265 50А 266 1АР 265 ЕИТ1 266 113 267 ЕОА 266 1АЗ 26У 2Н 10А 270 АОО 271 АОО 272 АОО 272 1АМЗ 276 1Н ЕМ?А 275 1МР 276 ЕВА 1НР ОЕС1310И Е1А 02 э+4 ЕЬЕЧЗ 035ЕТЕМ ЕЬЕЧЗ Е5ЕЧ1 15 Е8А Н0500 1 51 НО50С САЫ.,4(1:3) 1Р "2,4 22 Саьь,4(5:5) Е7 СШ+1.
4 Саьь+2,4 Саьь+3,4 СА11+4,4 Е7 14 Е2А НОАОС Подождать в течение 51 единицы времени. Верно ли,что САььСАЕ[РьООН) или САььОР[РАООМ) ф О? Если иеверно, то верно ли, что РАСОМ = 2? Если неверно, то верно ли,что САььООММ[РьООН) ЭА О? Если неверно, повторить шаг Е7. Е9. Установка и якато а бе ействля. (См. строку 202.) 02 (- О. Выполнить подпрограмму ОЕС1310М. Вернуться к моделированию других событий. 3 критические моменты; именно с ее помощью была подготовлена табл.
1. Эти подробности здесь опущены; онн довольно просты, но в значительной мере усложняют код. Было создано нескоцько языков программирования, которые позволяли упростить форму указания действий дискретного моделирования с последующей компиляцией этих указаний на машинный язык. В данном разделе язык ассемблера использовался, конечно же, потому, что здесь рассматривались основные методы управления связанными списками и подробности дискретного моделирования на компьютере, который способен выполнять последовательные, а не параллельные вычисления. Метод управления последовательностью сопрограмм на основе списка ЧА1Т или перечня действий, который описан в этом разделе, называется квазипараллельной обработкой (диаамрагаПе1 ргосеэипд).
Анализ времени выполнения такой длинной программы сделать довольно трудно, потому что она пронизана весьма сложными взаимосвязями. Однако большие программы часто тратят большую часть времени на выполнение сравнительно небольших процедур, которые осуществляют простые действия. Поэтому хорошую оценку общей производительности можно получить с помощью особой процедуры трассировки, или, иначе говоря, с помощью црофайлера (ргор(ег), которая выполняет программу и записывает, как часто выполняется та или иная команда.
Она позволяет обнаружить "уязвимые места" производительности программы, которым следует уделить особое внимание. [См. упр. 1.4.3.2-7. См. также Яойщаге Ргасбсе бг Ехреп'- епсе 1 (1971), 105 — 133, где приводятся примеры таких исследований для программ на языке РОВТВА.ч', произвольно выбранных из мусорных корзин Станфордского компьютерного центра (БсапГогб Сошрцсег Сепсег).[ Автор экспериментировал с программой моделирования работы лифта, запуская ее в течение 10000 единиц по моделируемой шкале времени и при условии, что в модели находится 26 человек.
Оказалось, что наиболее часто выполнялся цикл сортировки ЯОЕТ1в', строки 073-075, а именно — 1432 раза, тогда как процедура сортировки ЯОЕТ19 вызывалась 437 раз. Процедура СУСЛЕ выполнялась 407 раз, поэтому для увеличения скорости ее выполнения не следовало бы вызывать подпрограмму ВЕРЕТЕН в строке 095; лучше полностью включить в программу четыре строки этой подпрограммы (с зкономией 4и при каждом использовании СУСЛЕ). С помощью профайлера также бьшо обнаружено, что подпрограмма 0ЕС19109 вызывалась только 32 раза, а цикл на шаге Е4 (строки 217 — 219) выполнялся всего 142 раза.
Автор надеется, что при изучении этого примера читатель узнает столько же нового о моделировании, сколько автор узнал о работе лифтов. УПРАЖНЕНИЯ 1. [21] Предложите описание операций вставки и удаления данных с левого конца дважды связанного списка (1). (С учетом тех же операций на правом кон 1е, которые можно вывести из соображений симметрии, получим описание всех действий для дека общего типа ) 2. [22) Объясните, почему для односвязного списка нельзя выполнять операции так же эффективно, как для дека общего типа Удаление элементов может быть эффективно выполнено только с одного конца одиосвязного списка 3. [22[ В модели работы лифта из данного раздела для каждого этажа используются три переменные вызова (САььйр, САЯСАН и САьЫОНК), которые представляют нажимаемые кнопки.
Вполне возможно, что вместо трех лифту необходима только одна или две двоичные переменные для кнопок вызова на каждом этаже. Объясните, в какой последовательности экспериментатор должен нажимать кнопки в данной модели, чтобы доказатаь, что для каждого этажа (за исключением самого нижнего и самого верхнего) существуют трн независимые двоичные перемемные. 4. [24) Шаг Е9 в сопрограмме работы лифта обычно отменяется на шаге Еб; даже если ан не отменен, ом выполняет не очень большой объем работы. Объясните, при каких обстоятельствах лифт будет вести себя иначе, если шаг Е9 удалить из модели.
Например, может ли лифт иногда останавливаться на этажах в другом порядке? б. [20) В табл. 1 человек 10 появляется на этаже 0 в момент 1048. Покажите, что, если бы человек 10 появился на этаже 2, а ме ма этаже О, лифт отправился бы вверх, а не вниз после входа всех людей в кабину на этаже 1 несмотря на то, что человек 8 желает спуститься на этаж О. 6. [23) В период 1183-1233 в табл. 1 пассажиры 7-9 входят в кабину лифта на этаже 1; лифт спускается на этаж О, и из него выходит только пассажир 8.
Затем лифт снова останавливается на этаже 1, предположительно для того, чтобы взять пассажиров 7 и 9, которые уже находятся в кабиме лифта; таким образом, на этаже 1 лифт уже никто не ожидает. (Эта ситуация возникает в Калтехе довольно редко; если вы вошли в лифт, движущийся в ненужном вам направлении, вам придется снова сделать дополнительную остановку на пути к исходному этажу.) Во многих других типах лифтов пассажиры 7 и 9 не были бы взяты в лифт в момент 1183, так как индикаторы снаружи лифта показали бы, что ом движется вниз, а не вверх.
Им пришлось бы ожидать возвращения лифта. В описанной модели такие индикаторы не предусмотрены, а потому невозможно сказать, в каком направлении будет двигаться лифт, до тех пор,пока человек не попадет в кабину. Следовательно. табл 1 отражает реальную ситуацию. Какие изменения необходимо внести в сопрограммы П и Е, чтобы в описанной выше модели лифта использовались внешние индикаторы, благодаря которым людям не приходилось бы входить в кабину лифта, следующего в противоположном направлении? 7. [25] Часто программистам очень стыдно признавать свои ошибки в программах, но, если ошибки поучительны, о мнх не следует забывать; лучше сообщить о приобретенном опыте другим.
При создании программы из этого раздела автор совершил (среди прочих) следующую ошибку. строка 154 содержала команду "1АМЕ СУСЕКЕ" вместо?3АЕЕ 04А". Действительно, если лифт прибыл на этаж, нужный конкретному человеку, та больше нет необходимости 'отменять" шаг С4. Поэтому можно просто перейти к процедуре СУСЕЕ и продолжить моделирование других действий. В чем же заключается ошибка? 8.
[21] Создайте код лля выполнения шага Е8, строки 277 — 292, который опущен в программе из данного раздела. 9. [23) Создайте код для подпрограммы ЭЕС1816К, который опущен в программе из данного раздела. 10. [40) Вероятно, здесь стоит отметить,что, хотя автор пользовался лифтом в течение многих лет и думал, что довольно хорошо знает принцип его работы, только во время написания этого раздела он обнаружил новые факты об алгоритме выбора направления движения реального лифта. Шесть раз автору приходилось экспериментировать с лифтом, и всякий раз он думал, что уж теперь-то он окончательно понял его тода| орегамф.
(Теперь автор не склонен к продолжению этих экспериментов, так как опасается, что во время нового эксперимента обнажится еще одна новая грань поведения лифта, которая будет противоречить предложенному здесь варианту алгоритма.) Мы часто склонны недооценивать степень непонимания предмета, но лишь до тех пор, пока не попытаемся промоделировать его с помощью компьютера. Попробуйте описать действия некоторого хорошо знакомого вам лифта Проверьте свой алгоритм с помощью экспериментов (подглядывать в его электрическую схему— нечестно'), а затем создайте дискретную модель этой системы и запустите ее на компью- тере ° 11.
(21) (Фрагментарно обноеляемал помять.) Следующая проблема часто возникает в задачах синхронного моделирования Система имеет и переменных ч[1),,ч[п), и на каждом шаге моделирования новые значения некоторых из иих вычисляются на основе прежних Предполагается, что вычисления выполняются "одновременно" в том смысле, что этн переменные не принимают новых значений да тех пор, пока не будут выполнены все операции присвоения.
Таким образом, одновременное появление выражений Ч [1] Э в у[2] н у [2] г- Ч [Ц приведет к обмену значениями Ч[1] и Ч[2], это сильно отличается от того, что обычно происходит при последовательном вычислении Эту ситуацию, конечно же, можно промоделировать с помощью таблицы меУч [Ц, МЕМЧ[в]. Перед каждым шагом моделирования для этого следует установить МЕМЧ [А] э- у[А) для 1 < А < и, затем записать все изменения величин Ч[А] в МЕМЧ[А) и наконец установить Ч[А] с — ИЕМЧ[А], 1 < А < и Но этот "очень прямолинейный" метод не очень подходит по следующим причинам (1) часто п очень велико, а количество изменяемых переменных очень мало, (2) часто переменные упорядочены не в виде таблицы Ч [1),, Ч [и], а разбросаны в памяти самым произвольным образом, (3) этот метод не может обработать случай (что обычно является ошибкой), когда одна переменная принимает два значения на одном и том же шаге моделирования Предполагая, что количество изменяемых на одном шаге переменных очень мало, придумайте эффективный алгоритм, который моделирует нужные действия, используя две вспомогательные таблицы ИЕМЧ[А] и Е1МК[А)., 1 < А < и.
Если возможно, алгоритм должен обнаружить ошибку в случае, если одна переменная принимает два значения на одном и том же шаге. ° 12. (ЕЕ] Почему в описанной в этом разделе программе моделирования лучше использовать дважды связанные списки вместо однократно связанных или последовательных списков? 2.2.6. Массивы и ортогональные списки Одним из простейших обобщений линейного списка является двумерный (или, в более общем случае, многомерный) массив данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
