Да, Браун, 1988 - первая из известных мне статей, в которой описаны календарные очереди, хотя Браун упоминает нескольких авторов, которые предшествовали ему.Ниже приведена сравнительно полная библиография литературы по календарным очередям вместе с моими заметками по каждой статье.Оставьте мне комментарий, если вам нужны копии каких-либо публикаций.
- Vaucher 1975 Сравнение алгоритмов списка событий.Также представлены три новых алгоритма.Вдохновленный Brown1988.
- Алгоритм списка событий Henricksen 1977 - адаптируется к временным интервалам и хорошо работает с рядом распределений, основываясь на Vaucher и Duval
- Ulrich 1978 Brown1988 утверждает, что это O (1),за исключением списка переполнения
- Джонс 1986 Сравнивает очереди приоритетов, имеет раннюю версию очереди календаря
- Браун 1988 Представляет очередь календаря [aka: Очередь календаря с сортированной дисциплиной]
- Davison 1989 Обнаруживает то же самое, упоминает о некоторых важных улучшениях, Браун признает улучшения в том же письме и имеет некоторые собственные мысли.Дэвисон предполагает, что Джонс 1986 предложил несколько ценных механик календаря
- Роннгрен 1991 Ленивая очередь.Календарная очередь, которая имеет ближайшее, далекое и очень далекое будущее - это позволяет выполнять отложенную сортировку, что значительно ускоряет процесс тестирования
- Steinman 1994 Event Horizon.Сгенерированные события имеют некоторое распределение вероятностей, когда они происходят, давайте использовать это, чтобы определить, что нужно сортировать.Разрешить параллельное моделирование
- Steinman 1996 Event Horizon Part 2. Применяет Steinman1994 для управления списком событий.Изменяет другие структуры данных для использования в CQ.
- Ronngren 1997 Сравнение множества различных календарных очередей.Lazy Queue работает хорошо, но Brown1988 часто работает лучше.У LazyQ и SCQ плохая производительность в худшем случае, у Skew Heap и Sply Tree - худший в худшем случае.
- Oh 1997 Динамическая очередь отложенных календарей.Повышение производительности обычного CQ по сравнению с неравномерным распределением событий
- Oh 1999 Dynamic Calendar Queue.Хорошо работает с неравномерным распределением
- Cazzolla 1998 Java-реализация Lazy Queue с анализом (не академическая статья).
- Tan 2000 SNOOPy: статистически улучшено с оптимальным рабочим параметром CQ.Использует статистические тесты, чтобы сделать ведро ebtter.Работает до 100 раз быстрее, чем DCQ и CQ в определенных сценариях
- Диссертация на соискание степени бакалавра Хуэй, описывающая многие подробности статьи о Хуэй 2002, наряду с плюсами и минусами других реализаций очереди календаря
- Hui 2002 Futureсобытия не нужно сортировать прямо сейчас;следовательно, размер собственной очереди приоритетов может быть ограничен, что снижает накладные расходы на изменение размера.
- Goh 2003 MList.Многоуровневые связанные списки исключают операции изменения размера.Экспериментально показано, что по крайней мере на 100% быстрее, чем очередь календаря, динамический CQ, SNOOPy CQ, 2-уровневый динамический Lazy CQ и 3-уровневая Lazy Queue
- Siangsukone 2003 Оптимизированная ширина сегмента в CQ.Демонстрирует, что ширина сегмента может существенно повлиять на производительность.
- Goh 2004 DSplay.Исключите дорогостоящие операции по изменению размера.Как минимум на 100% быстрее, чем в других очередях календаря.
- Tang 2005 Ladder Queue.Обеспечивает стабильную производительность O (1) даже при распределении в очереди с бесконечной дисперсией.Похож на Lazy Queue, но лучше.
- Ян 2006 Вялая календарная очередь.Когда события в основном вставляются по порядку, можно использовать некоторые статистические свойства для достижения ускорения на 2 порядка
- Himmelspach 2007 События имеют длительность - вне основной линии исследования.Требовалась дополнительная функциональность, этот алгоритм предоставляет ее, но может иметь ограниченную последующую работу.
Кроме того, мы недавно закончили описание варианта алгоритма Брауна, который должен работать лучше.Описание, я думаю, вполне адекватно для построения реализации, и пример кода приведен в статье.Публикация озаглавлена Trading Space for Time: Constant-Speed Algorithms for Managing Future Events in Scientific Simulations Леманом, Кином и Барнсом и должна быть проиндексирована этой осенью.Если вам нужна копия, оставьте комментарий, и я отправлю его вам.
Чтобы ответить на другую часть вашего вопроса, вы можете рассматривать очередь календаря как приоритетную очередь, оптимизированную длясобытия, которые будут иметь постоянно уменьшающиеся приоритеты.Обычно приоритеты (времена) событий связаны каким-либо образом, чтобы избежать необходимости касаться всех событий, чтобы вставить их (как это может случиться в определенных формах управления кучей).