Дискретно-событийное моделирование

До сих пор мы двигали время маленькими равными шагами: dt, ещё dt, ещё dt. Но если между событиями ничего не происходит, мы тратим вычисления впустую. Дискретно-событийное моделирование переворачивает идею: часы прыгают сразу к следующему интересному моменту.

Дискретно-событийное моделирование (англ. discrete-event simulation, DES) — это способ симуляции, при котором состояние системы меняется только в дискретные моменты времени — события. Между событиями ничего не происходит, поэтому симулятор просто перескакивает от одного события к следующему.

Зачем это нужно? Представьте моделирование банка, который работает 8 часов. Если мы шагаем по секундам, это 28 800 шагов, и в большинстве из них вообще ничего не случается: никто не пришёл, никто не ушёл. DES обрабатывает только реальные события — приходы и уходы клиентов. Если за день их было 200, то и шагов будет около 400, а не 28 800. Выигрыш в скорости — десятки и сотни раз.

Два взгляда на время

Сравним два подхода к продвижению времени в симуляции.

Шаг по времени (time-stepped)

Мы выбираем шаг dt и на каждом шаге спрашиваем: «Что изменилось за этот интервал?» Так мы моделировали движение тел, рост популяций, ход эпидемии. Этот подход естественен, когда величины меняются непрерывно — координата, температура, численность.

Шаг по событиям (event-driven)

Здесь система меняется скачками: клиент либо пришёл, либо нет. Между этими скачками длина очереди постоянна. Тогда глупо проверять состояние каждую секунду — достаточно знать, когда произойдёт следующий скачок, и сразу перевести часы туда.

Ключевая структура DES — это список будущих событий (future event list). В нём хранятся запланированные события вместе с их временем. На каждой итерации мы достаём самое раннее событие, переводим часы на его время, обрабатываем его — и, возможно, планируем новые события в будущем.

Событийный цикл

Любая дискретно-событийная симуляция строится вокруг одного цикла:

пока есть будущие события:
    взять самое раннее событие
    перевести часы на его время
    обработать событие (возможно, запланировать новые)

«Взять самое раннее» — это операция «вынуть минимум». Для неё идеально подходит куча (heap, двоичная пирамида) из модуля heapq. Куча держит элементы так, что наименьший всегда наверху, а вставка и извлечение стоят дёшево — порядка log(n) операций.

Соберём минимальный, но настоящий событийный цикл. События — это пары (время, описание). Мы складываем их в кучу в произвольном порядке, а извлекаем строго по возрастанию времени.

import heapq

# (время, описание) — события в будущем
events = [(3.0, "приход A"), (1.5, "приход B"), (5.0, "уход A"), (2.0, "приход C")]
heapq.heapify(events)

clock = 0.0
while events:
    time, desc = heapq.heappop(events)
    clock = time
    print(f"t={clock:>4.1f}: {desc}")
print(f"Симуляция завершена в t={clock:.1f}")

Вывод:

t= 1.5: приход B
t= 2.0: приход C
t= 3.0: приход A
t= 5.0: уход A
Симуляция завершена в t=5.0

Обратите внимание: события мы записали вперемешку (3.0, 1.5, 5.0, 2.0), а обработали строго по порядку — 1.5, 2.0, 3.0, 5.0. Часы не шли равномерно: они прыгнули с 0.0 сразу на 1.5, потом на 2.0, потом сразу на 3.0 и наконец на 5.0. Промежутки между 2.0 и 3.0, между 3.0 и 5.0 мы просто пропустили — там ничего не происходило, и тратить на них время не нужно.

Как работает под капотом

Разберём механику по шагам.

Куча сравнивает кортежи. Когда в куче лежат пары (время, описание), Python сравнивает их поэлементно: сначала по первому элементу (времени), и только при равенстве — по второму. Поэтому heappop всегда отдаёт событие с минимальным временем. Если время совпадает, в дело идёт описание — поэтому полезно, чтобы вторым элементом было что-то сравнимое (число или строка), иначе при равном времени Python попытается сравнить несравнимое и упадёт.

Часы монотонны. В корректной DES часы только растут: каждое следующее извлечённое событие имеет время не меньше текущего. Это гарантируется самой кучей — мы всегда берём минимум из оставшихся. Поэтому строка clock = time никогда не двигает часы назад.

Формат вывода. Спецификатор {clock:>4.1f} означает: число с плавающей точкой, одна цифра после запятой, выровнять по правому краю в поле шириной 4 символа. Значение 1.5 занимает три символа («1.5»), поэтому слева добавляется один пробел: « 1.5». То же самое с 2.0, 3.0 и 5.0 — отсюда ведущий пробел в каждой строке вывода.

Схематично событийный цикл выглядит так:

      КУЧА БУДУЩИХ СОБЫТИЙ              ЧАСЫ
   [1.5 B][2.0 C][3.0 A][5.0 уход]      0.0
        |
   pop минимум --> (1.5, B)            прыжок --> 1.5
   pop минимум --> (2.0, C)            прыжок --> 2.0
   pop минимум --> (3.0, A)            прыжок --> 3.0
   pop минимум --> (5.0, уход A)       прыжок --> 5.0
        |
   куча пуста --> стоп                  5.0

В реальном симуляторе обработка события часто порождает новые события и кладёт их обратно в кучу. Например, «приход клиента» планирует «приход следующего клиента» и, если сервер свободен, «завершение обслуживания». Так список будущих событий живёт и пополняется, пока симуляция не достигнет конца времени или события не закончатся. Именно эту механику мы применим в следующем уроке к очереди M/M/1.

Частые ошибки

Двигать часы вручную, а не по событию. В DES часы должны равняться времени извлечённого события (clock = time), а не увеличиваться на фиксированный dt. Иначе теряется весь смысл подхода.
Класть в кучу несравнимые вторые элементы. Если при равном времени Python дойдёт до сравнения, например, двух словарей, он бросит TypeError. Кладите вторым элементом число-приоритет или строку, а полезную нагрузку — третьим.
Забыть про монотонность. Если событию назначить время меньше текущих часов, симуляция станет некорректной: «будущее» окажется в прошлом. Всегда планируйте новые события на clock + что-то положительное.
Использовать обычный список и сортировать его заново. Это работает, но медленно: пересортировка стоит дорого. Куча даёт извлечение минимума почти бесплатно.
Путать «нет событий» и «конец времени». Цикл может останавливаться либо когда куча пуста, либо когда часы перевалили за заданный горизонт. Это разные условия — выбирайте осознанно.

Итоги

Дискретно-событийное моделирование (DES) меняет состояние системы только в моменты событий, а между ними часы прыгают вперёд.
Это эффективнее шага по времени, когда «пустых» интервалов много: мы не тратим вычисления на ничегонеделание.
Ядро DES — список будущих событий, реализованный кучей (heapq): вставка и извлечение минимума за log(n).
Событийный цикл: достать самое раннее событие, перевести часы, обработать, при необходимости запланировать новые события.
Часы в корректной DES монотонны — они только растут, повторяя время извлекаемых событий.