Очередь календаря - Calendar queue

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

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

Выполнение

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

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

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

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

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

Рекомендации

• Р. Браун, «Календарные очереди: быстрая реализация очереди с приоритетом O (1) для задачи набора событий моделирования» CACM, Vol. 31, No. 10, pp. 1220-1227, октябрь 1988 г.
• Ричард М. Фудзимото. Параллельное моделирование дискретных событий. Сообщения ACM, 33 (10): 30–53, октябрь 1990 г.
• http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=899756