Этюды для программистов

подправлять положение каждого автомобиля. Если интервал достаточно мал, заметного накопления ошибок не произойдет, а выглядеть программа будет красиво — как семейство вложенных циклов. Однако при использовании метода пошаговой фиксации цикл может выполняться слишком большое число раз. В нашем случае эксперимент продлится примерно 12 минут модельного времени, в каждый момент на дороге будет около 90 машин, и, даже если выбрать большой интервал в одну десятую секунды, потребуется примерно 1200 циклов, или около 650 000 операций с отдельными автомобилями. Если программа тратит много времени на продвижение одного автомобиля, эксперимент слишком затянется. Положение можно подправить, варьируя интервал в зависимости от дорожной обстановки.

Другой подход состоит в том, чтобы подправлять положение автомобилей только в моменты критических событий. При таком подходе заводится список всех событий, ожидаемых в недалеком будущем; например, запускается или исчезает автомобиль, одна машина догоняет другую, прошло две минуты с момента исчезновения первого автомобиля, пора вновь ускорять автомобиль-виновник. Головным элементом списка событий всегда должно быть ближайшее событие; список в целом не обязан быть упорядоченным — его можно представить и как очередь с приоритетами, и как кучу. В основном цикле от списка отделяется головной элемент, описывающий очередное событие, все автомобили устанавливаются в позиции, соответствующие новому времени, запоминаются все события, которые следует планировать, эти события вставляются в список и список переупорядочивается, чтобы ближайшее событие оказалось в голове. Достоинство моделирования методом критических событий в том, что порой довольно долго, 4–5 секунд, ничего не происходит. Сэкономленное время можно употребить на более сложную обработку списка событий.

Инструментовка. Для решения этой задачи естественно воспользоваться языками моделирования, такими, как Симскрипт или Симула. Если они недоступны, подойдет любой процедурный язык. Независимо от метода моделирования существенным подспорьем будут хорошие структуры данных для представления информации об автомобилях и для реализации очереди событий.

Длительность исполнения. Одному исполнителю на 3 недели; еще неделя на изготовление фильма.

Развитие темы. Строго говоря, в предложенной задаче не изучается ситуация, описанная в нескольких первых абзацах. Вместо выяснения того, что происходит с ударной волной при различных средних скоростях движения на автостраде, в эксперименте рассматривались удары различной силы. Проделайте все еще раз, взяв диапазон начальных скоростей от 40 до 50 или от 60 до 70 миль в час. Попробуйте для некоторых переменных нормальное распределение вместо равномерного. Поварьируйте законы торможения и ускорения. Иными словами, изучите влияние всех параметров, а не только одного, выбранного нами.

Литература

Герман, Гардел (Herman R., Gardels К). Vehicular Traffic Flow. Scientific American, pp. 35–43, December 1963.

Авторы описывают проведение нескольких физических экспериментов над движением транспорта и развитие математической теории. Конечно, использовавшийся ими Голландский туннель в Нью-Йорке для большинства из нас недоступен Если вам интересно проследить за работами по этой тематике после 1963 г., научитесь пользоваться Science Citation Index или другими библиографическими средствами, помогающими довести старую информацию до наших дней.

18. Читаем, пишем, считаем, или Конструирование интерпретатора форматов

Вам, вероятно, пришлось написать по крайней мере одну программу, которая исторгала из машины бумажный поток, несущий искусно оформленные данные. Строка за строкой сомкнутыми рядами выступали из печатающего устройства целые батальоны чисел под предводительством четких заголовков. Интересовали вас только лишь два или три числа, но не напечатать всего было как-то неловко — ведь это так просто! А вдруг кому-то и в самом деле захочется узнать точную сумму налога для служащего 1793 на рабочем месте 907, выплаченную им в сентябре пять лет назад.

Выдать на печать такую уйму информации и не свалиться при этом от изнеможения вам удалось благодаря существованию таких вещей, как фортранные инструкции формата, которые помогли преобразовать эти неудобоваримые двоичные числа в радующие глаз цепочки из цифр, букв и знаков. По существу, то же самое происходит и при вводе. Вводные данные аккуратно пробиваются на перфокартах, и вы даже не задумываетесь о том, каким преобразованиям должны они подвергнуться для того, чтобы центральный процессор мог проделывать над ними свои несложные арифметические фокусы. А пожалуй, о вводе и выводе стоит поразмышлять чуть серьезнее. Программа, обрабатывающая большое количество данных, вполне может тратить от четверти до половины своего счетного времени на служебные подпрограммы ввода и вывода, а большая часть этого времени в свою очередь может уходить на интерпретирование форматов и преобразование данных. Вероятно, вы уже не будете так легкомысленно относиться к преобразованиям данных при вводе и выводе, если попытаетесь решить предлагаемую задачу, превратившись на время в системного программиста.

Для изучения были выбраны форматы языка Фортран, поскольку они просты, эффективны и были, в сущности, праотцами большинства других схем форматов. Всякий раз, когда в операции ввода/вывода участвует устройство, предназначенное для взаимодействия машины с человеком, связующим звеном между ними оказывается инструкция формата. Основные элементы, участвующие в операции ввода/вывода, — это список переменных, формат и файл. Элементы данных пересылаются из файла в переменные списка или в обратном направлении, в зависимости от того, какая операция — ввода или вывода — выполняется. При пересылке каждого элемента интерпретируется некоторая часть формата, достаточная для того, чтобы определить текстовое представление этого элемента в файле. Формат определяет лишь характер пересылки того или иного элемента данных, но объем перемещаемых данных от него не зависит.

Что такое формат?

Формат — это цепочка литер, описывающая преобразования данных, которые нужно выполнить. Поскольку формат всякий раз при использовании интерпретируется, то его можно рассматривать как маленькую программу. Формат общего вида имеет структуру

(yf¹s¹f²s²…fⁿsⁿz),

где n может быть нулем,

у и z — последовательности наклонных черточек, возможно пустые,

fⁱ — либо одиночный код формата, либо формат общего вида, перед которым может стоять натуральное число[25],

sⁱ — разделитель, т. е. последовательность из запятых и наклонных черточек, которая в некоторых случаях может быть пустой.

Пробелы в формате игнорируются везде, кроме одного случая, специально оговоренного ниже, а числа записываются в виде цепочек из десятичных цифр.

Предположим, произошло обращение к операции ввода/вывода. Указатель текущей позиции в файле устанавливается на начало следующей записи[26]. Курсор в формате устанавливается на начальную открывающую скобку и движется вправо либо до первого кода, которому должна соответствовать переменная в списке переменных, либо до правого края формата. Такой процесс позволяет при помощи инструкции вывода напечатать строку данных, не пересылая никаких данных из переменных. Интерпретатор форматов будет иметь некоторую внутреннюю память (организованную, как правило, в виде стека), которая будет освобождаться и на которую мы будем время от времени ссылаться, говоря, что интерпретатор что-либо «запомнил». Основной цикл просмотра формата прост. Интерпретатор получает очередную переменную из списка переменных. Курсор начинает двигаться вправо по формату в поисках такого кода, который соответствует передаче элемента данных из переменной в файл или обратно.