Очередь календаря

Календарная очередь (CQ) — это приоритетная очередь (очередь, в которой каждому элементу присвоен соответствующий приоритет, а операция удаления из очереди удаляет элемент с наивысшим приоритетом). Он аналогичен настольному календарю, который используется людьми для упорядочения будущих событий по дате. Для моделирования дискретных событий требуется структура списка будущих событий (FEL), которая сортирует ожидающие события по их времени. Такие симуляторы требуют хорошей и эффективной структуры данных , поскольку время, затрачиваемое на управление очередью, может быть значительным. Календарная очередь (с оптимальным размером сегмента) может достигать средней производительности O(1). Очереди календаря тесно связаны с очередями сегментов, но отличаются от них способом поиска и динамическим изменением размера.

Выполнение

Теоретически, как и очередь сегментов, календарная очередь состоит из массива связанных списков . Иногда каждый индекс в массиве также называют сегментом. Сегмент имеет указанную ширину, и его связанный список содержит события, временная метка которых соответствует этому сегменту. Настольный календарь имеет 365 сегментов на каждый день шириной в один день. Каждый элемент массива содержит один указатель , который является заголовком соответствующего связанного списка. Если имя массива — «месяц», то месяц[11] — это указатель на список событий, запланированных на 12-й месяц года (индекс вектора начинается с 0). Таким образом, полный календарь состоит из массива из 12 указателей и набора из 12 связанных списков. В календарной очереди постановка в очередь (добавление в очередь ) и удаление из очереди (удаление из очереди) событий в FEL зависит от времени события.

Пусть очередь календаря состоит из n сегментов шириной w . Тогда очередь события со временем t работает с сегментом ${\frac {t}{w}}\mod n$ . И более двух событий, запланированных в сегменте в соответствии с увеличенной меткой времени. Чтобы исключить события из очереди календаря, он отслеживает текущий год и день. Затем он ищет самое раннее событие в этом сегменте и удаляет его из очереди. (Напротив, очередь сегментов просто вернет любой элемент из первого непустого сегмента, не определяя, какой элемент в этом блоке является самым ранним.)

Операция изменения размера очереди календаря

Если количество событий в очереди намного меньше или намного больше количества сегментов, она не будет работать эффективно. Решение состоит в том, чтобы позволить количеству сегментов соответственно увеличиваться и уменьшаться по мере роста и сокращения очереди. Чтобы упростить операцию изменения размера, Nb (количество сегментов) в CQ часто выбирается равным степени двойки, т.е. $Nb=2^{n}$ ;↵

Количество сегментов удваивается или уменьшается вдвое каждый раз, когда Ne (количество событий) превышает 2 Nb или уменьшается ниже Nb /2 соответственно. При изменении размера Nb новую ширину w необходимо также рассчитать . Новое принятое значение w будет оцениваться путем выборки среднего временного интервала между событиями из первых нескольких сотен событий, начиная с текущей позиции сегмента. После этого будет создана новая очередь календаря, и все события в старом календаре будут перекопированы.

Ссылки

Браун, Р. (октябрь 1988 г.), «Очереди календаря: быстрая $O(1)$ реализация очереди приоритетов для проблемы набора событий моделирования», Communications of the ACM , 31 (10): 1220–1227, doi : 10.1145/63039.63045 , S2CID 32086497
Эриксон, К. Брюс; Ладнер, Ричард Э.; ЛаМарка, Энтони (2000), «Оптимизация очередей статического календаря», Транзакции ACM по моделированию и компьютерному моделированию , 10 (3): 179–214, doi : 10.1145/361026.361028
Фудзимото, Ричард М. (октябрь 1990 г.), «Параллельное моделирование дискретных событий» , Communications of the ACM , 33 (10): 30–53, doi : 10.1145/84537.84545 , S2CID 15054137
Тан, Ка Леонг; Тнг, Ли-Джин, «Очередь календаря SNOOPy», Материалы зимней конференции по моделированию 2000 г. , IEEE, doi : 10.1109/wsc.2000.899756 , S2CID 2982776